hdu2159 二維完全背包

#include <cstring>   
using namespace std;  
  
#define MAXN 105   
  
int n,m,k,s;  
  
int C[MAXN];  
int W[MAXN];  
int dp[MAXN][MAXN];  
int ans;  
//dp[i][j][k] = max(dp[i-1][j][k],dp[i][j-1][k-C[i]] + W[i]);   
//dp[j][k] = max(dp[j][k], dp[j-1][k-C[i]] + W[i]);   
  
int main()  
{  
    while(cin>>n>>m>>k>>s)  
    {  
        ans = 0;  
        for(int i = 1; i <= k; i++)  
        {  
            cin>>W[i]>>C[i];  
        }  
        memset(dp,0,sizeof(dp));  
        for(int e = 1; e <= k; e++)  
        {  
            for(int i = 1; i <= s; i++)  
            {  
                for(int j = C[e]; j <= m; j++)  
                {  
                    dp[i][j] = max(dp[i][j], dp[i-1][j-C[e]] + W[e]);  //完全背包   
                }  
            }  
        }  
        bool flag = false;  
        for(int i = 1; i <= m; i ++)  
        {  
            if(dp[s][i] >= n)  
            {  
                flag = true;  
                ans = i;  
                break;  
            }  
        }  
        if(flag)  
            cout<<m-ans<<endl;  
        else  
            cout<<"-1"<<endl;  
    }  
    return 0;  
}