引用：
题目:有N件物品和一个容量为V的背包。第i件物品的重量是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
【算法标签】01背包
【数据范围】1 ≤ N ≤ 3402，1 ≤ M ≤ 12880，1 ≤ Di ≤ 100，1 ≤ Wi ≤ 400
【思路1】看见楼下的大牛们的题解都很厉害，但鲜少有对01背包的公式进行详细地解释，蒟蒻我就来给后来的初学者讲解一下01背包的动态转移方程的含义。
01背包二维数组的动态转移方程为f[i][v] = max{f[i-1][v-w[i]]+c[i],f[i-1][v]}
其中，f[i][v]意为前i件，总重量小于等于v的最大价值（最优解），f[i-1][v-w[i]]+c[i]表示第i件物品放入背包中的最大价值，那么当前重量v就要减去第i件物品的重量（v-w[i]），再加上通过放入第i件物品所产生的价值c[i]；f[i-1][v]表示若第i件物品不放入背包内，那么自然当前的重量就不用减去第i件物品的重量，相应的价值也就不发生改变。取两者中的最大值，那么前i-1个物品的最大价值就是
max(f[i-1][v-w[i]]+c[i],f[i-1][v])。
【思路2】
如果你尝试用思路1来解决这道题，显然是不可行的，因为数组要开到f[3403][12881]，而这将意味着要开设43834043+3403+3403=43840849个变量！如果你将思路1的C++代码交付评测，你会发现要么是WC（Wrong Answer，错误的答案），要么是MLE（memory limit error，内存空间超出限制），有没有办法能将思路1压缩到一维数组呢？当然有。
一维数组的动态转移方程f[v] = max{f[v],f[v-w[i]]+c[i]}
意义和思路中的差不多，f[v]表示总重量小于等于v的最大价值，与思路1所不同的是，它省略了i这一参数，使方程更加简洁。
//My AC Code
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,fm[13000];
struct node{
int c,w;
}nm[3500];
bool cp(node a,node b){
if(a.w!=b.w)return a.w>b.w;
else return a.c<b.c;
}
int max(int a,int b){return a>b?a:b;}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&nm[i].c,&nm[i].w);
sort(nm+1,nm+n+1,cp);
//for(int i=1;i<=n;i++)printf("%d %d\n",nm[i].c,nm[i].w);
for(int i=1;i<=n;i++){
for(int j=m;j>=nm[i].c;j--){
fm[j]=max(fm[j],fm[j-nm[i].c]+nm[i].w);
}
}
printf("%d",fm[m]);
return 0;
}