二维的完全背包

二维的完全背包，状态转移方程： = max(dp[i][t], dp[i - b[j]][ t- 1] + a[j]);其中b[j]是要消耗的忍耐度,a[j]是获得经验，dp[i][t]就是消耗i 的忍耐度可以获得的最多经验！只要 dp[i][s]>=n时就可以停住了！

#include<iostream>
using namespace std;
int n,m,k,s;
int a[101],b[101],dp[101][101];

int max(int a,int b)
{
 return a=a>b?a:b;
}

int main()
{
     int i,j,t;
  freopen("D:\\input.txt","r",stdin);
  while(cin>>n>>m>>k>>s)
  {
       for(i=1;i<=k;i++)
    {
        cin>>a[i]>>b[i];
    }
    memset(dp,0,sizeof(dp));
    for(i=1;i<=m;i++)
    {
     for(t=1;t<=s;t++)
     {
      for(j=1;j<=k;j++)
      {
        if(i>=b[j])
        {
            dp[i][t]=max(dp[i][t],dp[i-b[j]][t-1]+a[j]);
        }
      }
     }
     if(dp[i][s]>=n)
      break;
    } 
    cout<<m-i<<endl;
  }
  return 0;
}