01背包的原型就是有N件物品和一个容量为V的背包。放入第i件物品耗费的空间是Ci，得到的价值是Wi，求将哪些物品装入背包可使获得的价值总和最大。而这道题的题意也就是这个意思，01背包的特点就是每种物品仅有一件，可以选择放或者不放。
下面是01背包的核心代码：
代码语言：javascript复制for(int i = 0; i < n; i ){
for(int j = V; j >= c[i]; j--){
dp[j] = max(dp[j] , dp[j-c[i]] w[i]);
}
}这个核心代码是由二维的状态转移方程优化来的(至于什么是状态转移方程捉着想知道怎么优化的自己去查一下吧~~)，懂了这个核心代码后01背包的问题就不是问题了。
AC代码：
代码语言：javascript复制#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 200005;
int dp[MAXN];
int val[MAXN]; // 价值
int c[MAXN]; // 体积
int n,m;
int main()
{
while(cin>>n>>m){
for(int i = 0;i<n;i ){
cin>>c[i]>>val[i];
}
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i ){
for(int j=m;j>=c[i];j--){
dp[j] = max(dp[j],dp[j-c[i]] val[i]);
}
}
cout<<dp[m]<<endl;
}
return 0;
}
/*
[来源] hiho Coder 1038
[题目]
01背包
[大意]
01背包模板题
[输入]
5 1000
144 990
487 436
210 673
567 58
1056 897
[输出]
2099
*/
