动态规划 - 背包问题

[Caaalabash]

翻山开始

[Caaalabash]

01背包问题

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

基本思路

这就是最基础的背包问题，每种物品只有一件，可以选择放或者不放，用f[i][v]表示前i件物品恰放入容量为v的背包可以获得的最大价值

若只考虑第i件物品的策略：

• 如果不放第i件物品，问题转化为：“前i-1件物品放入容量为v的背包中，价值为f[i-1][v]”
• 如果放第i件物品，问题转化为：“前i-1件物品放入容量为v-c[i]的背包中”

可以得到其状态转移方程：

f[i][v] = max{f[i-1][v], f[i-1][v-c[i]]+w[i]}

优化空间复杂度

上面的方法时间和空间复杂度均为O(VN)，空间复杂度可以优化到O(V)

观察状态转移方程可以发现：dp数组当前行的计算只用到了前一行前面列的值，这点可以利用滚动数组来优化

• 将二维数组优化为一维数组
• 第二层循环倒着遍历，保证了前面的值不会被新计算的值覆盖

优化后的状态转移方程为：

f[v] = max{f[v], f[v-c[i]]+w[i]}

[Caaalabash]

二维费用的背包问题

对于每件物品，具有两种不同的费用，选择这件物品必须同时付出这两种代价：对于每种代价都有一个可付出的最大值，问怎样选择物品可以得到最大的价值，假设第i件物品需要的两种代价为a[i]和b[i], 两种代价的最大值为A和B，物品的价值为w[i]

算法

费用较01背包问题加了一维，只需状态加一维即可，状态转移方程

f[i][a][b] = max{f[i-1][a][b], f[i-1][a-a[i]][b-b[i]]+ w[i]}

如前述方法，可以只使用二维数组：

f[a][b] = max{f[a][b], f[a-a[i]][b-b[i]] + w[i]}

[Caaalabash]

完全背包问题

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

基本思路

这个问题非常类似与01背包问题，不同的是每个物品有无限件，也就是对于每个物品，考虑的不是拿或者不拿，而是拿几件的问题

解法

for v=cost..V
  f[v] = max{f[v], f[v-c[i]] + w[i]}