Question

求解释01背包问题

一个旅行者有一个最多能用M公斤的背包，现在有N件物品，
第i件重量Wi,
价值Pi.
若每种物品只有一件 求旅行者能获得最大总价值
for i=1...N
for V=V...0
f[v]=max{f[v],f[v-w[i]]+p[i]}
为什么V要递减 这个方程是什么意思？
求详细解释！谢谢！

Answer 1

这个是状态转移方程
f[v] 表示背包剩余容量V时候积累的价值总和
你这个是优化版本的只用了一维数组 有个更基本的方法我解释给你听

有n件物品 假设当前到第i件了

{ f[i - 1][v];
f[i][v](到第i件时 此时容量为v ) = {
{ f[i - 1][v - w[i]] + p[i];（v>=w[i]）
(两者中较大的那个)

“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

Answer 2