Skip to main content

动态规划2-背包DP

December 15, 2018   

动态规划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滚动*