0/1背包
如果每个物体可以切分，称为一般背包问题，用贪心法求最优解，从最大的最多的开始。
如果每个物体不可分割，称为0/1背包问题。0和1代表装入背包和不装入背包。
举个栗子：有4个物品，其重量分别是2、3、6、5，价值分别为6、3、5、4，背包的容量为9。
先定一个二维数组dp[i][j]，i代表物品个数，j代表当前容量，dp[i][j]代表当前价值。
可以参照一下硬币问题的图。
从小问题扩展到大问题，先只装第一个物品，然后只装前两个物品，依次......直到装完。
在只装第一个物品的情况下，第一个物品重量为2，那么容量小于2的放不进去，因此dp[1][0]和dp[1][1]都为0，dp[1][2]=6，容量大于2的和等于2的一样(dp[1][3]=6......)。
只装前两个物品时，如果容量不能装第二个物品，就和只装第一个物品的情况相同，那么dp[i][j]=dp[i-1][j]，也就是dp[2][3]=dp[1][3]=6；如果能装第二个物品，又分为两种情况，如果装第二个物品，那么dp[2][3]=3，如果不装第二个物品，就和不能装的情况相同，dp[2][3]=6，因为要总价值最大，所以取两种情况的最大值，也就是max{dp[i-1][j]，dp[i-1][j-v(i)]+value(i)}，这里的dp[i-1][j]是不装第i个物品时的情况，dp[i-1][j-v(i)]+value(i)是装了物品i的情况，v(i)是i的容量，value(i)是i的价值，因为装了物品i，所以当前容量为j-v(i)（聪明的你肯定一看就懂，不懂就再想想）。
来，放题：
http://acm.hdu.edu.cn/showproblem.php?pid=2602
思路和上面一样。
代码：
#include<bits/stdc++.h> using namespace std; int t,n,c; int dp[1005][1005],v[1005],value[1005]; int main() { scanf("%d",&t); while(t--){ memset(dp,0,sizeof(dp)); scanf("%d%d",&n,&c);//n是骨头数量，c是背包体积 for(int j=0;j<n;j++){ scanf("%d",&value[j]);//价值 } for(int k=0;k<n;k++){ scanf("%d",&v[k]);//体积 } for(int x=1;x<=n;x++){ for(int y=0;y<=c;y++){ if(v[x]>y){//容量不能装第x个物品时 dp[x][y]=dp[x-1][y];//价值和上一个一样 } else dp[x][y]=max(dp[x-1][y],dp[x-1][y-v[x]]+value[x]);//能装时，求两种情况较大值以得最大价值 } } printf("%d ",dp[n][c]); } return 0; }
最后有一个滚动数组的技巧，处理dp[][]状态数组时把它变成一维的dp[]以节省空间，因为第x行由x-1行推出，所以可以直接覆盖上一行。
滚动数组代码：
int dp[1005];//原来是int dp[1005][1005] for(int x=1;x<=n;x++){//其余部分省略了，和上面一样 for(int y=c;y>=v[x];y--){//当然你也可以边读边处理 dp[y]=max(dp[y],dp[y-v[x]]+value[x]); } }
因为会遇到较大的数据量，所以为了节省空间使用滚动数组（空间复杂度从O(NV)减少为O(V)），但是时间复杂度上没有优化，并且因为它覆盖了中间转移状态，只留下了最后的状态，导致无法输出背包的具体方案。
更新：
01背包变形：https://www.luogu.com.cn/problem/P1164
思路：因为每一个菜要么吃要么不吃，所以当钱足够买这个菜的时候方法数为吃这个菜的方法数+不吃这个菜的方法数，当钱不够时就没法买，方法数为上一道菜的方法数。设dp[][]为方法总数，那么当目前拥有的钱j小于这一道菜价格a[i]时，dp[i][j]=dp[i-1][j]；注意当j等于这个菜价格的时候，可以只买这一道菜，dp[i][0]就等于1，或者可以判断当j==a[i]时，dp[i][j]=dp[i-1][j]+1；当j大于a[i]时，也就是说前i个物品中所有能凑出j-a[i]元的方案再加上当前这道菜品，dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]。
代码：
#include<iostream> #include<algorithm> #include<stdio.h> using namespace std; int a[105]; int dp[105][10005]; int main() { int n,m; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(j<a[i]) //钱不够买这道菜时，方法数为前一道菜的方法数 dp[i][j]=dp[i-1][j]; else if(j==a[i]) //注意特别判断刚好能买这一道菜的时候，dp[i][0]=1 dp[i][j]=dp[i-1][j]+1; else //钱够的时候，方法数为买这道菜和不买的方法数的和 dp[i][j]=dp[i-1][j]+dp[i-1][j-a[i]]; } } printf("%d ",dp[n][m]); return 0; }
https://www.luogu.com.cn/problem/P1510
笑死，做的时候感觉思路没问题，就一道模板题，结果wa了，回头一看让输出剩下的最大体力。
0/1背包：
https://www.luogu.com.cn/problem/P1048
http://acm.hdu.edu.cn/showproblem.php?pid=1864
http://acm.hdu.edu.cn/showproblem.php?pid=2955
滚动数组：
https://www.luogu.com.cn/problem/P2871
http://acm.hdu.edu.cn/showproblem.php?pid=1024
http://acm.hdu.edu.cn/showproblem.php?pid=4576
http://acm.hdu.edu.cn/showproblem.php?pid=5119
EOF