若有一些物品,和一个背包,每个物品有一定价值和重量,背包负重限定,请问怎样装东西进背包使价值最大?

来源：学生作业帮编辑：大师作文网作业帮分类：数学作业时间：2024/11/14 08:54:43

若有一些物品,和一个背包,每个物品有一定价值和重量,背包负重限定,请问怎样装东西进背包使价值最大?
编号：重量：价值
1：2：4 2：3：9 3：5：6 4：7：12 5：9：11 6：3：5 7：4：6 8：7：11 9：9：14
背包重量限制20

37=9+12+5+11(2,4,6,8)20=3+7+3+7
i:2, v:3,c[2]=3,w[2]=9, f[0]=0, old f[3]=4, new f[3]=9
i:4, v:10,c[4]=7,w[4]=12, f[3]=9, old f[10]=19, new f[10]=21
i:6, v:13,c[6]=3,w[6]=5, f[10]=21, old f[13]=25, new f[13]=26
i:8, v:20,c[8]=7,w[8]=11, f[13]=26, old f[20]=36, new f[20]=37
再问：麻烦解释以下计算过程
再答：首先用ci、wi代表第 i 种物品的重量、价值，然后我们将在总重量不超过Y的前提下，前 j 种物品放入背包的最大总价值定义为A(j, Y)。 A(j, Y)的递推关系为： A(0, Y) = 0 A(j, 0) = 0 A(j, Y) = max { A(j - 1, Y), wj + A(j - 1, Y - cj) }, j=1,2,...,9 通过计算A(9, 20)即得到最终结果（dp）。伪代码：　　for i=1 to 9 　　for v=20 to 0 　　f[v]=max{f[v],f[v-c[i]]+w[i]}; //由于A(j,Y)计算出后，A(j-1,Y)不再有用，这里左侧f[v]代表A(j,v)，右侧f[v]代表A(j-1,v)
再问：是否可能会存在问题？因为物品价值并不一定随物品重量增加？？
再答：不存在，你可以举例试一试

算法分析与设计题目请求解0/1/2背包问题：有1个背包、其容量为C,有n种物品（每个物品种类i都自己的重量wi和价值v 求PASCAL背包问题和无限背包思路和程序我有一个背包.“背包”的“背”的读音是什么? pascal 0/1背包和完全背包的差别? 一道物理题为：旅游登山时,背包中的物品有轻有重,怎样摆放能使人不容易向后倾到?把重的物品放到背包上部.说废话的走开! 背包有哪些品牌聚酯纤维和尼龙哪种背包质量更好? 因为我的一个红色背包忘记在了504房间,里面有我对我来说很重要的物品.翻译成英语句子. 如图所示，旅游登山时背包中的物品有轻有重，单从物理角度考虑，应该怎样摆放更科学呢？（　　）初三英语作文~急!假设你在上学的路上,和你的好朋友捡到了一个双肩背包,你们想找到失主,请根据背包里的东西做出推测,这是谁 01背包问题的贪心K阶优化算法设计(物品不可拆分）驴友和背包客的区别背包客旅游就是深度游还是穷游么?具体差别是什么呢?穷游泳有英文定义么?