完全+二维
最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？
Input
输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)
Output
输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。
Sample Input
10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2
Sample Output
0
-1
1
分析
n,m,k，s分别代表经验值，忍耐程度，种类，数目。一般情况下我们应该求的就是一个最大经验值，这是背包的一般问题，这道题只是稍稍变形，我们先假设题问的就是忍耐程度为m，杀怪数为s时，可获得最大的经验值是多少。
首先看一下，这是一个二维的背包问题，因为因为代价有两个，分别是忍耐程度，和数目，因为是二维所以我们很难直观的用图表来表示，所以我们类比一维代码来考虑这个问题
一维完全背包：
题目是这样的：对于吃货来说，过年最幸福的事就是吃了，没有之一！
但是对于女生来说，卡路里（热量）是天敌啊！
资深美女湫湫深谙“胖来如山倒，胖去如抽丝”的道理，所以她希望你能帮忙制定一个食谱，能使她吃得开心的同时，不会制造太多的天敌。
当然，为了方便你制作食谱，湫湫给了你每日食物清单，上面描述了当天她想吃的每种食物能带给她的幸福程度，以及会增加的卡路里量。
Input
输入包含多组测试用例。
每组数据以一个整数n开始，表示每天的食物清单有n种食物。
接下来n行，每行两个整数a和b，其中a表示这种食物可以带给湫湫的幸福值（数值越大，越幸福），b表示湫湫吃这种食物会吸收的卡路里量。
最后是一个整数m，表示湫湫一天吸收的卡路里不能超过m。
[Technical Specification]
2. 0 <= a,b <= 100000
2. 0 <= a,b <= 100000
1. 1 <= n <= 100
2. 0 <= a,b <= 100000
3. 1 <= m <= 100000
Output
对每份清单，输出一个整数，即满足卡路里吸收量的同时，湫湫可获得的最大幸福值。
Sample Input
5
1 1
5 3
10 3
6 8
7 5
6
Sample Output
20
for(i = 0;i<n;i++)
{
int j = m;
for(j = w[i];j<=m;j++)
{
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
}
用一个图表来表示就是这样的：
再来分析二维完全背包：
for(i = 0;i<k;i++)
for(j = 1;j<=s;j++)
for(l = w[i];l<=m;l++)
{
dp[j][l] = max(dp[j][l],dp[j-1][l-w[i]]+v[i]);
}
dp[i][j]两维，两维分别表示两种代价，三层for循环，第一层与一维背包类似，第二维第三维两种代价的顺序不是固定的，无论哪一维在前面循环都是可以的，求其本质就是就是一维固定，去找另一维的一个一维背包问题。
AC代码：
#include <stdio.h>
#include <memory.h>
#include <algorithm>
using namespace std;
const int Max = 110;
int v[Max];
int w[Max];
int n,m,k,s;
int dp[Max][Max];
int main()
{
while(scanf("%d %d %d %d",&n,&m,&k,&s) != EOF)
{
int ans = 0;
memset(dp,0,sizeof(dp));
int i =0;
for(i = 0;i<k;i++)
{
scanf("%d %d",&v[i],&w[i]);
}
int j,l;
for(i = 0;i<k;i++)
for(j = 1;j<=s;j++)
for(l = w[i];l<=m;l++)
{
dp[j][l] = max(dp[j][l],dp[j-1][l-w[i]]+v[i]);
}
if(dp[s][m] >= n)
{
for(i = 0;i<=m;i++)
{
if(dp[s][i] >= n)
{
ans = m- i;
break;
}
}
}
else
{
ans = -1;
}
printf("%d\n",ans);
}
return 0;
}