![]() |
可以分享下目前你觉得比较好用的AI助手吗 |
题目
有 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 件物品耗费的费用是 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个物体,
不放第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个物品没有顺序关系,任意排放都满足上述关系
当前公式也只是是用于该问题,并不是所有动态规划都能使用该公式,每个动态规划的问题都是要推导它的状态迁移方程
我讲的也不是很清楚,建议看一下《算法图解》这本书
@GoroutineLeak 没呢,最近在刷算法题,感觉动态规划的难一点
过早客微信公众号:guozaoke • 过早客新浪微博:@过早客 • 广告投放合作微信:fullygroup50 鄂ICP备2021016276号-2 • 鄂公网安备42018502001446号