一个旅行者的背包可以装12Kg物品.docVIP

习题 1、一个旅行者的背包可以装12Kg物品，他可以从5件物品中选择若干件物品放在背包中，每件物品的价值和重量分别是Cj和Wj (j=1,2,……5),具体数值见下表 。他应该选择哪几件物品放在背包内，使携带的物品价值最大？ 物品 1 2 3 4 5 重量/kg 3 4 3 4 6 价值/百元 12 12 9 16 30 解析： 1）背包问题的动态规划解题思路： 有件物品和一个容量为V的背包。第i件物品的是c[i]，价值是 [i]。求解将哪些物品装入背包可使价值总和最大。状态转移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的 伪码：??for i=1.. ???for v=V..0 ????f[v]=max{f[v],f[v-c[i]]+w[i]};如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 重量 3 4 3 4 6 价值 12 12 9 16 30 Fmax=30； （2）物品数为两件： 物品 1,2 1,3 1,4 1,5 2,3 2,4 2,5 3,4 3,5 4,5 重量 7 6 7 9 7 8 10 7 9 10 价值 24 21 28 42 21 28 42 25 39 46 Fmax=46； （3）物品数为三件： 物品 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 重量 10 10 13 10 12 13 11 价值 33 37 0 37 51 0 37 Fmax=51; （4）物品数为四件： 物品 1,2,3,4 1,2,4,5 1,3,4,5 2,3,4,5 重量 14 17 16 17 价值 0 0 0 0 由以上可知价值最大为5100元，选择的物品为1,3,5. 程序为： program knapsack； const maxm=12; maxn=5； type ar=array[0..maxn] of integer; var m,n,j,i,t:integer; c,w:ar; f:array[0..maxm] of integer; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); f(0):=0; for i:=1 to m do for j:=1 to n do begin if i=w[j] then t:=f[i-w[j]]+c[j]; if tf[i] then f[i]:=t end; writeln(f[m]); end 2、枚举序列x1,x2,x3,x4,x5 ，n={1,2,3，4,5}一切可能的组合，有K^n种选择，如何进行遍历。 分析：枚举的一切可能的组合，对每一可能组合，先取x1,x2,x3 这一组合，它对应于枚举树的第一层的分支，对进行分析后，保持 x1 和 x2 ，另取 x3 进行计算，在固定 x1 和x2 的前提下穷尽 x3一切可能的取值，下一步可以回朔一个层次，对一个分支直到末端计算和判别，然后回朔到上一层在对另一完整分支计算和判别，这一枚举过程可由计算机语言的多重循环来实现。 程序代码： #includestdio.hvoid main(){enum number {x1,x2,x3,x4,x5}; number pri; int i,j,k,n,loop; n=0; for(i=x1;i=x5;i++) for(j=x1;j=x5;j++) if(i!=j) for(k=x1;k=x2;k++) if((k!=i)(k!=j)) n=n+1; printf(%4d,n); for(loop=1;loop=3;loop++) switch(loop) {case 1:pri=number(i);break; case 2:pri=number(j);break; case 3:pri=number(k);break;