设有背包问题实例,n=7,(w0,w1,w2,w3,w4,w5,w6)=(2,3,5,7,1,4,1),(p0,p1,p2,p3,p4,p5,p6)=( 10,5,15,7,6,18,3),M=15。求这一实例的最优解及最大收益.
0/1背包问题是一种特殊的背包问题,装入背包的物品不能分割,只允许或者整个物品装入背包,或者不装入,即xi=0,或1,(0<=i
设有带时限的作业排序实例n=7,收益(p0, p1, p2, p3, p4, p5, p6)=(3,5,20,18,1,6,30),作业的时限(d0, d1, d2, d3, d4, d5, d6)=(1,3,4,3,2,1,2),请用贪心算法求解此实例的最优解和最大收益。
到商场购买商品需要找零钱。假设有四种面值分别为14角、5角、2角和1角的硬币可以找零,售货员希望找零的硬币数目最少。也就是,优化目标是找零的硬币数目最少,限制条件是所选择的硬币的总面值等于要找的零钱数。(1),给出贪心法求解找零钱问题的最优量度标准;(2),假设要找的零钱数分别是13角,21角和41角;给出相应的解。