背包问题总结(未完待续)
1. 背包问题
题目
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品的耗费是 Ci,其价值为 Wi。求解将哪些物品装入背包可使价值总和最大。
状态转移方程
dp[i, v] = max(dp[i - 1, v], dp[i - 1, V - Ci] + Wi
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品的耗费是 Ci,其价值为 Wi。求解将哪些物品装入背包可使价值总和最大。
dp[i, v] = max(dp[i - 1, v], dp[i - 1, V - Ci] + Wi
相关推荐