01背包问题：对于一些每个物品只有一个的选择问题

装箱问题：

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

在 n 个物品中，任选若干个装入箱内，使箱子的剩余空间为最小。

输入格式：

第一行是一个整数 V，表示箱子容量。

第二行是一个整数 n，表示物品数。

接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

可以将空间看作是价值，求的是空间最大，也就是价值最大。

代码如下：

#include
using namespace std;
const int N = 20010;
int n, V;
int f[N];
int main() {int v;cin >> V >> n;for (int i = 0; i < n; i++) {cin >> v;for (int j = V; j >= v; j--)f[j] = max(f[j], f[j - v] + v);}cout << V - f[V];return 0;
}

注意:最后输出的是剩余多少空间。

宠物小精灵之收服：

小智想收服一些小精灵。

对于每一个野生小精灵而言，小智可能需要使用很多个精灵球才能收服它，而在收服过程中，野生小精灵也会对皮卡丘造成一定的伤害。

当皮卡丘的体力小于等于0或者精灵球用完时，小智就必须结束狩猎。

小智的目标有两个：主要目标是收服尽可能多的野生小精灵；如果可以收服的小精灵数量一样，小智希望皮卡丘受到的伤害越小。

输入格式：

输入数据的第一行包含三个整数：N，M，K，分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。

输出格式：

输出为一行，包含两个整数：C，R，分别表示最多收服C个小精灵，以及收服C个小精灵时皮卡丘的剩余体力值最多为R。

两个条件限制的01背包问题，像普通01背包一样做就行，只是加一层循环。最后输出f[n][m]（n个球，m个体力）。要输出剩下的体力值，我们遍历f[n][0]~f[n][m]即可。

题目要求当体力为0的时候算抓捕失败，所以我们把m-1当做m带入计算即可。

代码如下：

#include
using namespace std;
const int N=1010;
int f[N][N];
int n,m,k;//拥有的球数和体力值、精灵数
int main(){cin>>n>>m>>k;int a,b;//每只精灵需要的球数和照成的伤害for(int i=0;i>a>>b;for(int j=n;j>=a;j--)//遍历球数for(int u=m-1;u>=b;u--)//遍历体力f[j][u]=max(f[j][u],f[j-a][u-b]+1);}int tmp=0;for(int i=m;i>=0;i--)if(f[n][i]==f[n][m-1])tmp=i;cout<