[简化背包问题]设有一个背包可以放人的物品重量为s，现有n件物品，重量分别为w1，w2，…，wn。请设计从

这n件物品中选择若干件放入此背包，使得放入的物品重量之和正好为s的递归算法和非递归算法。

答案

查看答案

发布时间：2021-07-20

更多“[简化背包问题]设有一个背包可以放人的物品重量为s，现有n件物品，重量分别为w1，w2，…，wn。请设计从”相关的问题

第1题

(背包问题)设有一个背包可以放入的物品的重量为5，现有n件物品，重量分别为w[1]，w[2]，…，w[n]。间

（背包问题)设有一个背包可以放入的物品的重量为5，现有n件物品，重量分别为w[1]，w[2]，…，w[n]。间

能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真);否则称此背包问题无解(或称其解为假)。试用递归方法设计求解背包问题的算法。(提示：此背包问题的递归定义如下：)

点击查看答案

第2题

0-1背包问题:给定n种物品和一背包。物品i的重量是w,其价值为v，背包的容量为C。编写算法实现选择装入背包的物品，使得装入背包中物品的总价值最大。

点击查看答案

第3题

考虑一个背包问题，共有n=5个物品，背包容量为W=10，物品的重量和价值分别为：w={2，2，6，5，4}，v={6,3，

5，4，6}，求背包问题的最大装包价值。若此为0-1背包问题，分析该问题具有最优子结构，定义递归式为

其中c(i，j)表示i个物品、容量为j的0-1背包问题的最大装包价值，最终要求解c(n,W)。采用自底向上的动态规划方法求解，得到最大装包价值为(62)，算法的时间复杂度为(63)。若此为部分背包问题，首先采用归并排序算法，根据物品的单位重量价值从大到小排序，然后依次将物品放入背包直至所有物品放入背包中或者背包再无容量，则得到的最大装包价值为(64)，算法的时间复杂度为(65)。

A.11

B.14

C.15

D.16.67

点击查看答案

第4题

对于0-1背包问题的解向量X，Xi=1表明选择物品1i。（)

点击查看答案

第5题

举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。

点击查看答案

第6题