经典ACM算法合集经典ACM算法合集(11)

经典ACM算法合集经典ACM算法合集

问题形式化描述：给定C＞0， wi ＞0， vi ＞0，1≤i≤n，要求n 元0-1向量( x1 ， x2 ，…， xn )，xi = 0或1，1≤i≤n，使得，而且达到最大。
2、题目分析：
考虑到每种物品只有2 种选择，即装入背包或不装入背包，并且物品数和背包容量已给定，要计算装入背包物品的最大价值和最优装入方案，可用回溯法搜索子集树的算法进行求解。

3、算法设计：
a. 物品有n种，背包容量为C，分别用p[i]和w[i]存储第i种物品的价值和重量，用
x[i]标记第i种物品是否装入背包，用bestx[i]存储第i种物品的最优装载方案；
b. 用递归函数Backtrack (i,cp,cw)来实现回溯法搜索子集树（形式参数i表示递归深
度，n用来控制递归深度，形式参数cp和cw表示当前总价值和总重量，bestp表示当前
最优总价值）：
① 若i >n，则算法搜索到一个叶结点，判断当前总价值是否最优：
1> 若cp>bestp，更新当前最优总价值为当前总价值（即bestp=cp），更新
装载方案（即bestx[i]=x[i]( 1≤i≤n)）；
② 采用for循环对物品i装与不装两种情况进行讨论（0≤j≤1）：
1> x[i]=j；
2> 若总重量不大于背包容量（即cw+x[i]*w[i]<=c），则更新当前总价
值和总重量（即cw+=w[i]*x[i],cp+=p[i]*x[i]）, 对物品i+1调用递归函
数Backtrack(i+1,cp,cw) 继续进行装载；

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(11)全文阅读和word下载服务。