摘要：背包问题题目给定种物品和一个容量为的背包，物品的体积是，其价值为。用子问题定义状态其状态转移方程是。
P01: 01背包问题
题目
给定 N 种物品和一个容量为 V 的背包，物品 i 的体积是 wi，其价值为 ci 。
(每种物品只有一个)
问：如何选择装入背包的物品，使得装入背包中的物品的总价值最大？
面对每个物品，我们只有选择放入或者不放入两种选择，每种物品只能放入一次。
我们用之前同样的思路来走一遍试试
假设只剩下最后一件物品，我们有两种选择
1.剩余空间足够时，选择放入
2.剩余空间不足时，不放入
所以我们有两个最优的子结构：
1.容量为V的背包放入i-1件物品的最优选择
2.容量为V-w[i]的背包放入i-1件物品的最优选择
所以，综合起来就是：
i 件物品放入容量为V的背包的最优选择：
max(容量为V的背包放入i-1件物品的最优选择，容量为V-w[i]的背包放入i-1件物品的最优选择+c[i])
我们用f[i] [v]表示前 i 件物品放入容量为 v 的背包中可以获得的最大价值。
用子问题定义状态：
其状态转移方程是：f[i] [v] = max{f[i-1] [v],f[i-1] [v-w[i]]+c[i]}。
我们先假设
背包总容量为V = 12
物品的容量数组为 w = [4, 6, 2, 2, 5, 1]
价值数组为 c = [8, 10, 6, 3, 7, 2]
f(i,v) = 0 (i<=1, v
f(i,v) = c[0] (i==1, v>=p[0]);
f(i,v) = f(i-1,v) (i>1, v
f(i,v) = max(f(i-1,v), f(i-1,v-w[i-1])+c[i-1])(i>1, v>=w[i-1])
我们每次从左至右，保存前一次的数据
从上至下时，保存前一行的数据
所以我们总的来说只用保存一行的数据，空间复杂度为O(V)
时间复杂度为O(N*V),空间复杂度为O(V);
但是，如果我们用原始的递归办法去做，即排列组合的方法去做时
时间复杂度为O(2^N);
那么当V很大，N较小时，比如V=1000，N=6时，用递归只用计算2^6=64次，而备受推崇的动态规划就需要计算1000*6=6000次
所以说，算法没有绝对的好坏，关键要看应用的惨景
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/96773.html
摘要：背包问题具体例子假设现有容量的背包，另外有个物品，分别为，，。最后，就是动态规划的思路了。而前个物体放入容量为的背包，又可以转化成前个物体放入背包的问题。 背包问题具体例子：假设现有容量10kg的背包，另外有3个物品，分别为a1，a2，a3。物品a1重量为3kg，价值为4；物品a2重量为4kg，价值为5；物品a3重量为5kg，价值为6。将哪些物品放入背包可使得背包中的总价值最大？ 首先...
摘要：动态规划概念动态规划过程每次决策依赖于当前状态，又随即引起状态的转移。相关文章王者编程大赛之一王者编程大赛之二蓄水池王者编程大赛之四约瑟夫环王者编程大赛之五最短路径 首发于 樊浩柏科学院 服务目前每月会对搬家师傅进行评级，根据师傅的评级排名结果，我们将优先保证最优师傅的全天订单。 showImg(https://img3.fanhaobai.com/2017/12/2017-ziro...
摘要：首先说下算法对于前端的作用和应用作用不用说了提高效率和性能应用目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。 首先说下算法对于前端的作用和应用 作用：不用说了提高效率和性能 应用：目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。，自己买的哭着也要读完，不扯了，直...
摘要：首先说下算法对于前端的作用和应用作用不用说了提高效率和性能应用目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。 首先说下算法对于前端的作用和应用 作用：不用说了提高效率和性能 应用：目前也是买了算法导论这本书，看得头晕，各种数学知识需要返回去重新认识，哎，终于知道了以前学的东西总有用的。。。，自己买的哭着也要读完，不扯了，直...
阅读 2796·2021-11-25 09:43
阅读 942·2021-10-11 10:57
阅读 2446·2020-12-03 17:20
阅读 3677·2019-08-30 14:05
阅读 2381·2019-08-29 14:00
阅读 1959·2019-08-29 12:37
阅读 1627·2019-08-26 11:34
阅读 3167·2019-08-26 10:27
