题目
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的费用是 Ci1，得到的
价值是 Wi。求解将哪些物品装入背包可使价值总和最大。
1.2 基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即 F [i; v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得
的最大价值。则其状态转移方程便是：
F [i， v] = max{F [i − 1， v]，F [i − 1， v − Ci] + Wi}
这不是很简单么，状态转移方程就是表示这个：
第i件物体放入背包后的最大价值F [i， v]，是 1）可以选择放第i件商品(F [i − 1， v − Ci] + Wi) 或不放(F [i − 1， v])的最大值啊 。
这就是动态规划(DP)的思想吧，网上看下DP。
题目 描述有误 “放入第 i 件物品耗费的费用是 Ci1” 应该是 “放入第 i 件物品耗费的容量是 Ci1”
每件物品耗费的空间，用数组表示 costs={ C0,C1...Ci .. Cn }
每个物品是可以考虑装进背包，也可以考虑不装进背包的
我们从左到右依次判断
定义函数F(i,v) 表示 从左到右，遍历了第i个物品，而且用了总容量v，的最大价值
那么F(i,v) 如何取最大呢，
case 1 不选取物品i,那么此时的价值 = 上次的物品i-1,并且容量v的最大价值
case 2 选取物品i,那么此时价值增加Wi,但是容量减少Ci因为总容量为v,那么上次的最大价值为F(i-1,v-Ci)
当遍历完所有物品后
那么最终最大值 为 F(n,v)
不放第3个物体的价值公式 : F [i − 1， v]
F [i − 1， v]表示的就是在容量为v时其中前2个物品的最大价值
放第3个物体的价值公式 : F [i − 1， v − Ci] + Wi
Ci是第3个物品的容量,Wi是第3个物品的价值
v − Ci是为了装下第3个物品剩下的容量
F [i − 1， v − Ci] 表示在容量为(v − Ci)时前2个物品的最大价值
F [i − 1， v − Ci] + Wi 表示 容量为(v − Ci)时前2个物品的最大价值 + 第3个物品的价值
容量为v时,3个物品的最大价值就是
max(不放第3个物体的价值, 放第3个物体的价值)
放与不放第3个物品的价值都是基于放前2个物品的最大价值算出来的,因此就转变成了子问题
注:这里的第n个物品只是方便理解,实际上3个物品没有顺序关系,任意排放都满足上述关系
当前公式也只是是用于该问题,并不是所有动态规划都能使用该公式,每个动态规划的问题都是要推导它的状态迁移方程
我讲的也不是很清楚,建议看一下《算法图解》这本书
认证信息