0-1背包问题的回溯算法，下面的解释不正确的是

A.解空间树是子集树#B.左(1)分支的剪枝：选择装入背包的物品重量之和超出背包容量就剪枝#C.右（0）分支的剪枝：已装入背包内的物品价值和+剩余物品装剩余背包容量所能获得的最大价值（物品可分割，也就是用背包问题的贪心算法求得的最大价值）＞当前最优值bestp, 就剪枝.#D.当搜索至叶子结点时，一定是发现了到目前为止最好的解

答案

使用约束函数剪去不合理的左子树（装该物品）。;使用限界函数剪去得不到更优解的右子树（不装该物品）。

如搜索结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装赏学吧APP，拍照搜题省时又省心！

更多“0-1背包问题的回溯算法，下面的解释不正确的是”相关的问题

第1题

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

A.利用价值最大的贪婪准则时，选物品1，这种方案的总价值为60

B.最优解选物品为2和3，总价值为80

C.使用贪婪准则，不能保证得到最优解

D.利用价值最大的贪婪准则时，选物品2和3，总价值为80

点击查看答案

第2题

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

A.利用价值密度最大的贪婪准则时，选物品1，这种方案的总价值为60

B.最优解选物品为2和3，总价值为80

C.使用贪婪准则，能保证得到最优解

D.利用价值密度最大的贪婪准则时，选物品2和3，总价值为80

点击查看答案

第3题

回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。

A.深度优先

B.广度优先

C.活结点优先

D.扩展结点优先

点击查看答案

第4题

考虑背包问题，n=6，物品重量W=（1,5,2,3,6,1），价值P=（15,59,21,30,60,5），背包承重量C=10，能放进背包的物品价值最大的是（）。

A.101

B.110

C.115

D.120

点击查看答案

第5题

子集和问题：给定n个不同的正整数，已知其和大于c，问有多少个不同的其和等于c的子集？下面给出的算法，解空间树是子集树，且n个数已按从小到大有序存放于a数组中。 void backtrack（int i) { if（sum==c) count++; else if（i<=n) { if（sum+a[i]<=c) { sum+=a[i]; backtrack（i+1); 【】 } } } 请将【】位置缺失的代码补齐，从下面选项中找到答案。

A.sum-=a[i];

B.sum-=a[i]; backtrack(i+1);

C.backtrack(i+1);

D.backtrack(i+1); sum-=a[i];

点击查看答案

第6题

0-1背包问题不能用贪心算法求解，因为它不满足最优子结构性质。

点击查看答案

第7题

子母弹优化设计是一个典型的背包问题。

点击查看答案

第8题