题解 P2722 【总分 Score Inflation】
想弄懂完全背包题，当然是要先看01背包喽！作为一个刚刚学会背包一个星期的蒟蒻，我决定把我弄懂01背包和完全背包的过程分享给更多蒟蒻。
01背包
题目描述
一个旅行者有一个最多能装 M 公斤的背包，现在有 n 件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn，求旅行者能获得最大总价值。
【输入】
第一行：两个整数，M (背包容量，M≤200)和N(物品数量，N≤30）
第2..N+1 行：每行二个整数Wi，Ci，表示每个物品的重量和价值。
【输出】
仅一行，一个数，表示最大总价值。
下面是01背包模板代码，最下面有样例数据
#include<iostream>
using namespace std;
const int maxm=201,maxn=31;
int m,n;
int w[maxn],c[maxn];
int f[maxn][maxm];//表示前i个物品在容量为v下可以获得的
最大总价值
int main()
{
cin>>m>>n;//背包容量m和物品数量n
for(int i=1;i<=n;i++){
cin>>w[i]>>c[i];//输入每个物品的质量和价值
}
for(int i=1;i<=n;i++){
for(int v=m;v>0;v--){
if(w[i]<=v){
f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
}
//f[i][v]表示前i件物品，总体积（质量）不超过v的最优价值
else{
f[i][v]=f[i-1][v];
}
}//个人习惯，每个循环都带括号，方便添加代码
}
cout<<f[n][m];//f[n][m]为最优解
return 0;
}f[i-1][v-w[i]]这东西代表的就是在v的空间下，放入w[i](也就 是第i件物品）后再放之前的物品获得的价值。[v-w[i]]就是现在 的体积减掉该物品体积后剩下的，就是可以前i件物品留下的， 在之前的计算中已经求得了前i件物品可以得到的价值.
它具有自动检索一般的功能，比如样例中我们在i=4时，它根据 [v-w[i]]找到了此时除了它剩下的空间放前面物品最多可以获得3 的价值，再加上它的9的价值得到12。同时它还和只放3个物品进行比较，如果第四个物品价值过小，程序将会选择不拿4。
当我把 输入数据第四个物品和第三个物品的价值改为7时，发现f[3][10] 就已经达到了最大值11，程序在i=4时没有更改结果
以下是通过文件操作打出来的数据
输入:
10 4
2 1
3 3
4 5
7 9
输出： 12
测试输出：
（每段数据有10个，第i段数据代表i等于几时的f[i][1..10],每次的第一个数据代表本次操作时的 v）
10 1
9 1
8 1
7 1
6 1
5 1
4 1
3 1
2 1
1 0
10 4
9 4
8 4
7 4
6 4
5 4
4 3
3 3
2 1
1 0
10 9
9 9
8 8
7 8
6 6
5 5
4 5
3 3
2 1
1 0
10 12
9 10
8 9
7 9
6 6
5 5
4 5
3 3
2 1
1 0
下面是用一维数组实现01背包
（用的本题数据和字母）但本题不是01背包题（因为每个种类中你可以选择若干道题，而不是只能做一道或不做），所以下面代码无法通过
#include<iostream>
using namespace std;
int x,y;
int t[10002],p[10002];
int f[10002];
int main()
{
int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>p[i]>>t[i];
}
for(int i=1;i<=n;i++){
for(int t1=m;t1>=t[i];t1--){
f[t1]=max(f[t1],f[t1-t[i]]+p[i]);
}
}
cout<<f[m];
return 0;
}这里我们可以看到，它省去了数组中用来表示前i个物品（题目）的一维，因为这不重要。我们不需要管它是在前几个物品（题目）中在容量v（时间t）下得到的最大价值（最高分数），我们只需要知道在容量v下可以得到的最大价值。所以现在的f[100002]就是代表在多少容量（时间）下可以得到的最高价值（分数）。其余都和上面的背包模板一样。
好，现在就是完全背包了
下面是AC代码
#include<iostream>
using namespace std;
int x,y;
int t[10002],p[10002];
int f[10002];
int main()
{
int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++){
cin>>p[i]>>t[i];
}
for(int i=1;i<=n;i++){
for(int t1=t[i];t1<=m;t1++){//注意这一行
f[t1]=max(f[t1],f[t1-t[i]]+p[i]);
}
}
cout<<f[m];
return 0;
}
也许没有我的“注意这一行”，你可能找不出来它和上面的01背包代码有什么区别。这也正说明了完全背包和01背包的相似。他们的差别只有第二重for循环的差别。
在01背包中，t1从m一直减到t【i】，保证了每个物品在一个t1中只会被放一次。 而完全背包中，从t1一直加到m，使在可以放下的情况下尽量多地放。