天天看点

动态规划背包问题matlab,经典动态规划:完全背包问题 · Issue #298 · labuladong/fucking-algorithm · GitHub...

这里的j-coins[i-1]不应该是j-coins[i-1]*k吗?(k等于任意整数)

意思就是,不应该是可以拿任意枚i硬币都是要求的吗?

你这里的理解是错误的。

dp[j-coins[i-1]]这里是把你说的这几种情况给包括了的,比如这里

动态规划背包问题matlab,经典动态规划:完全背包问题 · Issue #298 · labuladong/fucking-algorithm · GitHub...

在完全背包问题中,一个物品可以拿多次。如图上半部分所示,假设我们遍历到物品 i = 2, 且其体积为 w = 2,价值为 v = 3;对于背包容量 j = 5,最多只能装下 2 个该物品。那么我们的状 态转移方程就变成了 dp[2][5] = max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)。如果采用这种方法,假设 背包容量无穷大而物体的体积无穷小,我们这里的比较次数也会趋近于无穷大,远超 O(NW) 的 时间复杂度。

怎么解决这个问题呢?我们发现在 dp[2][3] 的时候我们其实已经考虑了 dp[1][3] 和 dp[2][1] 的情况,而在时 dp[2][1] 也已经考虑了 dp[1][1] 的情况。因此,如图下半部分所示,对于拿多个 物品的情况,我们只需考虑 dp[2][3] 即可,即 dp[2][5] = max(dp[1][5], dp[2][3] + 3)。这样,我们 就得到了完全背包问题的状态转移方程:dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v),其与 0-1 背包问 题的差别仅仅是把状态转移方程中的第二个 i-1 变成了 i。

可以看到dp[2][5] = max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6) = max(dp[1][5], (dp[1][3], dp[1][1] + 3) +3) =

max(dp[1][5], dp[2][3] +3)