二维费用的背包问题是指：对于每件物品，具有两种不同的费用，选择这件物品必
须同时付出这两种费用。对于每种费用都有一个可付出的最大值（背包容量）。问怎样
选择物品可以得到最大的价值。
设第 i 件物品所需的两种费用分别为 Ci 和 Di。两种费用可付出的最大值（也即两
种背包容量）分别为 V 和 U。物品的价值为 Wi。
有时，“二维费用”的条件是以这样一种隐含的方式给出的：最多只能取 U 件物品。

http://acm.hdu.edu.cn/showproblem.php?pid=2159

二维费用背包之完全背包

#include <cstdio>
#include<algorithm>
#include<string.h>
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
using namespace std;
int main()
{
    int n,m,k,s;
    int dp[105][105];
    int cost[105];
    int exp[105];
    while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=k;i++)
        {
            scanf("%d%d",exp+i,cost+i);
        }
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=s;j++)
            {
                for(int q=cost[i];q<=m;q++)
                {
                    dp[j][q]=Max(dp[j][q],dp[j-1][q-cost[i]]+exp[i]);
                }
            }
        }
        if(dp[s][m]<n)
        {
            printf("-1\n");
        }
        else
        {
            int tmp=0;
            for(int i=1;i<=m;i++)
            {
                if(dp[s][i]>=n)
                {
                    tmp=i;
                    break;
                }
            }
            printf("%d\n",m-tmp);
        }
    }

}