背包总结

1. 01背包

问题描述：有n件物品，每件物品的重量为w[i]，价值为c[i]，现有容量为V的背包，如何放入使背包的总价值最大。
解：dp[i][v]表示第i件物品恰好放入容量为v的背包中所能获得的最大值
dp[i][v]=max{dp[i-1][v],dp[i-1][v-w[i]]+c[i]}(1<=i<=n,w[i]<=v<=V)
边界dp[0][v]=0
实现：因为dp[i][v]只和dp[i-1][v]的状态有关，所以可以用1*V的数组表示每一轮的dp值，i从1到n，v从V到w[i]
剪枝优化：dp[V]=V的时候退出

for(int i=1;i<=n;i++)
  for(int v=V;v>=w[I];v--)
      dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
例题：洛谷P2639

2.完全背包
问题描述：每个物品都有无限件

for(int i=1;i<=n;i++)
  for(int v=w[I];v<=V;v--)
      dp[v]=max(dp[v],dp[v-w[i]]+c[i]);

3.多重背包
问题描述：每种物品都有有限个数量
解：可以看成是多个有着相同价值和重量的物品，转化成01背包