题目内容
（请给出正确答案）
设有一个背包可以放入的物品重量为s，现有n件物品，重量分别为w1，w2，…，wn。请设计从这n件物品中选择若干件放入此背包，使得放入的物品重量之和正好为s的递归算法和非递归算法。
简答题官方参考答案
（由简答题聘请的专业题库老师提供的解答）
更多“设有一个背包可以放入的物品重量为s，现有n件物品，重量分别为w1，w2，…，wn。请设计从这n件物品中选择若干件放入”相关的问题
有载重量为 M 的背包,n 种物品的重量及价值分别
。如果每个物品只有一件,求一种最优装法,使得装入背包的物体价值最大。考虑回溯算法。先对物品按照
从大到小进行排序,并用序列< 重量,价值 >来表示排好序以后的物品序列。对如下给定实例:
排序后的结果是:
用
=1或 0来分别表示取用或者不用物品 i。那么在搜索树的节点
处的代价函数为:
A、
B、
C、
D、
【说明】
“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1；w2，……，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。
如下程序均能求得“背包问题”的一组解，其中程序4.1是“背包问题”的递归解法，而程序4.2是“背包问题”的非递归解法。
【程序4.1】
include＜stdio.h＞
define N 7
define S 15
int w[N+1]={0，1，4，3，4，5，2，7}；
int knap(int s，int n)
{ if(s==0)return 1；
if(s＜0||(s＞0& &n＜1))return 0；
if((1)))|
printf("%4d"，w[n])；return 1；
} return (2)；
}
main(){
if(knap(S，N))printf("OK!\n")；
else printf("NO!\n")；
}
【程序4.2】
include＜stdio.h＞
define N 7
define S 15
typedef struct{
int s；
int n：
int job；
} KNAPTP；
int w[N+1]={0，1，4，3，4，5，2，7}；
int knap(int s，int n)；
main(){
if(knap(S，N))printf("OK!\n")；
else printf("NO!\n")；}
int knap(int s，int n)
{ KNAPTP stack[100]，x；
int top，k，rep；
x.s=s；x.n=n；
x.job=0；
top=|；Stack[top]=x；
k=0；
while((3)){
x=Stack[top]；
rep=1；
while(!k && rep){
if(x.s==0)k=1；/*已求得一组解*/
else if(x.s＜0||x.n ＜=0)rep＝0；
else{x.s＝(4)；x.job＝1；
(5)=x；
}
}
if(!k){
rep=1；
while(top＞＝1&&rep){
x=stack[top--]；
if(x.job==1){
x.s+=W[x.n+1]；
x.job=2；
Stack[++top]=x；
(6)；
}
}
}
}
if(k){/*输出一组解*/
while(top＞=1){
x＝staCk[top--]；
if(x.job＝＝1)
printf("%d\t"，w[x.n+1])；
}
}
return k；
}
【说明】
“背包问题”的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，w2，…，wn。希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。
如下程序均能求得“背包问题”的一组解，其中程序1是“背包问题”的递归解法，而程序2是“背包问题”的非递归解法。
【程序1】
include＜stdio.h＞
define N 7
define S 15
int w[N+1]={0,1,4,3,4,5,2,7};
int knap(int s, int n)
{
if(s==0) return 1;
if(s＜0 || (s＞0 && n＜1))return 0;
if((1)){/*考虑物品n被选择的情况*/
printf("%4d",w[n]);
return 1;
}
return (2);/*考虑不选择物品n的情况*/
}
main()
{
if(knap(S,N))printf("OK!\n");
else printf("N0!\n");
}
【程序2】
include＜stdio.h＞
define N 7
define S 15
typedef struct{
int s;
int n;
int job;
}KNAPTP;
int w[N+1]={0,1,4,3,4,5,2,7};
int knap(int s, int n);
main()
{
if(knap(S,N)) printf("0K!\n");
else printf("N0!\n");
}
int knap(int s, int n)
{
KNAPTP stack[100],x;
int top, k, rep;
x.s=s;x.n=n;
x.job=0;
top=1; stack[top]=x;
k=0;
while((3) ){
x=stack[top];
rep=1;
while(!k && rep){
if(x.s==0) k=1;/*已求得一组解*/
else if(x.s＜0 || x.n＜=0) rep=0;
else{
x.s=(4);
x.job=1;
(5)=x;
}
}/*while*/
if(!k){
rep=1;
while(top＞=1 && rep){
x=stack[top--];
if(x.job==1){
x.s +=w[x.n+1];
x.job=2;
stack[++top]=x;
(6);
}/*if*/
}/*while*/
}/*if*/
/*while*/
if(k){&nbs
阅读下列程序说明和C代码，将应填入(n)处的字句写在答题纸的对应栏内。
【程序4．1说明】
"背包问题"的基本描述是：有一个背包，能盛放的物品总重量为S，设有N件物品，其重量分别为w1，w2，．．．，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S。
如下程序均能求得"背包问题"的一组解，其中程序4．1是"背包问题"的递归解法，而程序4．2是"背包问题"的非递归解法。
【程序4．1】
#include
#define N 7
#define S 15
int w［N+1］={0，1，4，3，4，5，2，7}；
int knap(int s，int n)
{ if(s==0)return 1；
if (s<0||(s>0& &n<1))return 0；
if((1) )){
printf(″%4d″，w［n］)；return 1；
}return (2) ；
}
main(){
if(knap(S，N))printf(″OK!＼n″)；
else printf(″N0!＼n″)；
}
【程序4．2】
#include
#define N 7
#define S 15
typedef struct {
int s；
int n：
int job；
} KNAPTP；
int w［N+1］={0，1，4，3，4，5，2，7}；
int knap (int s，int n)；
main() {
if (knap (S，N)) printf (″OK!＼n″)；
else printf (″NO!＼n″)；}
int knap (int s，int n)
{ KNAPTP stack［100］，x；
int top，k，rep；
x．s=s；x．n=n；
x．job=0；
top=l；stack［top］=x；
k=0；
while((3) ) {
x=stack ［ top ］；
rep=1；
while (!k && rep ) {
if (x．s==0)k=1；/*已求得一组解*/
else if (x.s<0 || x．n <=0)rep=0；
else{x．s= (4) ；x．job=1；
(5) =x；
}
}
if(!k){
rep=1；
while(top>=1&&rep){
x=stack［top--］；
if(x．job==1){
x．s+=w［x．n+1］；
x．job=2；
stack［++top］=x；
(6) ；
}
}
}
}
if(k){/*输出一组解*/
while(top>=1){
x=stack［top--］；
if(x．job==1)
printf(″%d＼t″，w［x．n+1］)；
}
}
return k；
}
A、0－1 背包问题和背包问题都可用贪心算法求得最优解
B、0－1 背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
C、0－1 背包问题不能用贪心算法求最优解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
D、因为 0－1 背包问题不具有最优子结构性质，所以不能用贪心算法求解
警告：系统检测到您的账号存在安全风险
为了保护您的账号安全，请在“简答题”公众号进行验证，点击“官网服务”-“账号验证”后输入验证码“”完成验证，验证成功后方可继续查看答案！
