阅读下列函数说明和C代码，填入(n)处字句，并回答相应问题。[说明]背包问题就是有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，而且选中物品的价值之和为最大。背包问题是一个典型的NP完全难题。对该问题求解方法的研究无论是在理论上，还是在实践中都具有一定的意义。如管理中的资源分配、投资决策、装载问题等均可建模为背包问题。常用的背包问题求解方法很多，但本题中采用了一种新的算法来求解背包问题。该算法思想为：首先要对物品进行价重比排序，然后按价重比

题目

阅读下列函数说明和C代码，填入(n)处字句，并回答相应问题。

[说明]

背包问题就是有不同价值、不同重量的物品n件，求从这n件物品中选取一部分物品的选择方案，使选中物品的总重量不超过指定的限制重量，而且选中物品的价值之和为最大。

背包问题是一个典型的NP完全难题。对该问题求解方法的研究无论是在理论上，还是在实践中都具有一定的意义。如管理中的资源分配、投资决策、装载问题等均可建模为背包问题。

常用的背包问题求解方法很多，但本题中采用了一种新的算法来求解背包问题。该算法思想为：首先要对物品进行价重比排序，然后按价重比从大到小依次装进包裹。这种方法并不能找到最佳的方案，因为有某些特殊情况存在，但只要把包中重量最大的物品取出，继续装入，直到达到limitweight，这时的物品就是limit weight的最大价值。这种算法不需要逐个进行试探，所以在数据非常大时，执行效率主要由排序的时间复杂度决定。该算法的流程图为图11-4。

仔细阅读程序说明和C程序流程图及源码，回答问题1和问题2。

[流程图11-4]

[程序说明]

struct Thing：物品结构

typedef struct Bag：背包结构类型

input ( )：将物品按序号依次存入数组函数

inbag ( )：物品按物价比入包函数

init ( )：初始化函数

sort ( )：对物品按价格重量比排序函数

outbag ( )：取出包中weiht最大的物品函数

print ( )：最佳方案输出函数

[C程序]

define N 255

struct Thing {

double weight;

double value;

double dens;

}thing[N];

typedef stmct Bag {

Thing thing [N];

double weighttmp;

double sumvalue;

}bag,best;

inbag ( )

{

do{

bag.thing[i]=thing[i]

(1)

(2)

i++;

}while ( (3) )

}

init ( )

{

for (inti=0; i＜N; i++)

{

input (thing[i].weight, thing [i].value)

thing [i].dens=thing[i].value/thing [i].weight;

};

}

main ( )

{

init ( );

sort ( );

inbag ( );

do {

best=bag; //把包中物品放入暂存数组

outbag ( ); //取出包中weight最大的物品

(4)

}while ( (5))

print (best)； //输出temp因为是最佳方案

}

根据程序说明及流程图、部分C源码，充分理解算法思想，填入(n)处。

相似考题

1.背包问题就是给定n种物品和一个背包，设Wi为物品i的重量，Vi为其价值，C为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物品总价最大。用贪婪算法解决背包问题，贪婪准则为：每次都选择价值最大的物品装包。假设n=3；W1=100，V1=60；W2=20，V2=40；W3=20，V3=40；C=110。下列说法不正确的是（）A．利用价值最大的贪婪准则时，选物品1，这种方案的总价值为60B．最优解选物品为2和3，总价值为80C．使用贪婪准则，不能保证得到最优解D．利用价值最大的贪婪准则时，选物品2和3，总价值为80

2.背包问题就是给定n种物品和一个背包，设Wi为物品i的重量，Vi为其价值，C为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物品总价最大。用贪婪算法解决背包问题，贪婪准则为：每次都选择价值最大的物品装包。假设n=3；W1=100，V1=50；W2=20，V2=30；W3=20，V3=40；C=110。下列说法正确的是（）A．选物品1，这种方案的总价值为50B．选物品2和3，总价值为70C．使用贪婪准则，能保证得到最优解D．选物品1和3，总价值为90

3.133、背包问题就是给定n种物品和一个背包，设Wi为物品i的重量，Vi为其价值，C为背包的重量容量，要求在重量容量的限制下，尽可能使装入的物品总价最大。用贪婪算法解决背包问题，贪婪准则为：每次都选择Vi/Wi 值（价值密度）最大的物品装包。假设n=3；W1=100，V1=50；W2=20，V2=30；W3=20，V3=40；C=110。下列说法正确的是（）A．选物品1，这种方案的总价值为50B．选物品2和3，总价值为70C．使用贪婪准则，不能保证得到最优解D．选物品1和3，总价值为90

4.0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。用动态规划法编写算法和程序实现0-1背包问题。并给出如下测试用例的求解过程：有5件物品，重量分别为（3，2，1，4，5）,价值分别为（25,20,15,40,50)，背包容量w=6。

参考答案和解析

正确答案：(1)bag.weighttmp=bag.weighttmp+thing[i].weight; (2)bag.sumvalue=bag.sumvalue+thing[i].value; (3)bag.weighttmp=weightlimit (4)inbag( )； (5)best.sumvaluebag.sumvalue
(1)bag.weighttmp=bag.weighttmp+thing[i].weight; (2)bag.sumvalue=bag.sumvalue+thing[i].value; (3)bag.weighttmp=weightlimit (4)inbag( )； (5)best.sumvaluebag.sumvalue

题目

相似考题

参考答案和解析

相关内容