动态规划2-背包DP

装箱问题

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 输入描述：一个整数v，表示箱子容量；一个整数n，表示有n个物品；接下来n个整数，分别表示这n 个物品的各自体积 输出描述：一个整数，表示箱子剩余空间。 样例输入: 24 6 ​ 8 3 12 7 9 7 样例输出：0

状态：f[i][j]表示前i个物品能否装满j的体积

for(int i=1;i<=n;i++)
for(int j=1;j<=v;j++)
    f[i][j]=f[i-1][j] || f[i-1][j-v[i]];
for(int i=v;i>0;i++)
    if(f[n][i]) printf("%d",v-i);

优化

• 01滚动

  f[i][j]中每一次的状态转移只与上一行有关系，所以只需要一个2层的数组，可以用&1实现

• 就地滚动

  每一次都会由左边的值转移到现在，所以每一次只要将循环从右往左就可以了

01背包

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

##方法1：动态规划 状态：还是一样，每一个背包只有选或者不选两种决策，这道题多了一个条件，相当于状态多了一个维度 转移方程：f[i][j][k]=f[i-1][j][k]||f[i-1][j-v[i]][k-c[i]] *i维度可以01滚动*