在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明算法的正确性）
题目
在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明算法的正确性）
相似考题
更多“在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明算法的正确性）”相关问题
-
第1题：
【问题 1】（8 分）
用回溯法求解此 0-1 背包问题，请填充下面伪代码中（1）～（4）处空缺。
回溯法是一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND( v,w,k,W )函数，其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的最优解，则该结点无需再扩展。
下面给出 0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。
变量说明如下：
cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。
正确答案：
（1）k←1或其等价形式（2）cw←cw+w[k]或其等价形式（3）k←k–1或其等价形式（4）k←k+l或其等价形式 -
第2题：
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。【说明】0-1背包问题定义为:给定1个物品的价值v[1....i]、重量w[1....i]和背包容量T,每个物品装到背包里或者不装到背包里,求最优的装包方案,使得所得到的价值最大。0-1背创问题具有最优子结构性质,定义c为最优装包方案所获得的最大价值则可得到如下所示的递归式。
【C代码】下面是算法的C语言实现(1)常量和变量说明T:背包容量V[]:价值数组W[]:重量数组C[][]:c[i][j]表示前i个物品在背包容量为j的情况下最优装包方案所能获得的最大价值(2)C程序
【问题1】(8分)根据说明和C代码,填充C代码中的空(1)~(4)【问题2】(4分)根据说明和C代码,算法采用了(5)设计策略。在求解过程中,采用了(6)(自底向上或者自顶向下)的方式。【问题3】(3分)若5项物品的价值数组和重量数组分别为v[]={0,1,6,18,22,28}和w[]={0,1,2,5,6,7},背包容量为T=11,则获得的最大价值为(7)。答案：解析：问题1:1:c[i][j]2: temp第3题：
有0-1背包问题如下： n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），单位重量物品价值（7.5，2.67，1.5，0.8，0.375，0.1）
正确答案: 可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。
1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。
2.把重量为3的物品放进背包，此时剩余载重量为14，P为23；
3.把重量为4的物品放进背包，此时剩余载重量为10，P为29；
4.把重量为5的物品放进背包，此时剩余载重量为5，P为33；
由于8>5，所以不能再放进背包。
结果是把重量为2，3，4，5的物品装进背包，总价值最大为33。第4题：
对于0－1背包问题和背包问题的解法，下面（）答案解释正确。
- A、0－1背包问题和背包问题都可用贪心算法求解
- B、0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
- C、0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
- D、因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解
正确答案:C第5题：
一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？
正确答案:按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解。第6题：
有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？
正确答案: 因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15+8+6+4=33，为最大值。第7题：
描述0-1背包问题。
正确答案:已知一个背包的容量为C，有n件物品，物品i的重量为Wi，价值为Vi，求应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。第8题：
单选题关于0－1背包问题以下描述正确的是（）A可以使用贪心算法找到最优解
B能找到多项式时间的有效算法
C使用教材介绍的动态规划方法可求解任意0－1背包问题
D对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题
正确答案： B解析： 暂无解析第9题：
问答题有0-1背包问题如下： n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大。 P=（15，8，6，4，3，1），W=（2，3，4，5，8，10），单位重量物品价值（7.5，2.67，1.5，0.8，0.375，0.1）正确答案： 可知随着物品的重量增加，物品的价值减少；因此可以用贪心算法来求解。以选取单位重量物品价值高为贪心策略。
1.先把重量为2的物品放进背包，此时剩余载重量为17，P为15。
2.把重量为3的物品放进背包，此时剩余载重量为14，P为23；
3.把重量为4的物品放进背包，此时剩余载重量为10，P为29；
4.把重量为5的物品放进背包，此时剩余载重量为5，P为33；
由于8>5，所以不能再放进背包。
结果是把重量为2，3，4，5的物品装进背包，总价值最大为33。解析： 暂无解析第10题：
问答题举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。正确答案： 举例如：
p{7，4，4}，w={3，2，2}，c=4时，
由于7/3最大，
若按题目要求的方法，只能取第一个，收益是7。
而此实例的最大的收益应该是8，取第2，3 个。解析： 暂无解析第11题：
填空题0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。正确答案： O(n*2n),O(min{nc,2n})解析： 暂无解析第12题：
单选题对于0－1背包问题和背包问题的解法，下面（）答案解释正确。A0－1背包问题和背包问题都可用贪心算法求解
B0－1背包问题可用贪心算法求解，但背包问题则不能用贪心算法求解
C0－1背包问题不能用贪心算法求解，但可以使用动态规划或搜索算法求解，而背包问题则可以用贪心算法求解
D因为0－1背包问题不具有最优子结构性质，所以不能用贪心算法求解
正确答案： A解析： 暂无解析第13题：
● （65） 不能保证求得0-1 背包问题的最优解。
（65）
A. 分支限界法
B. 贪心算法
C. 回溯法
D. 动态规划策略
正确答案：B
第14题：
0-1背包问题的回溯算法所需的计算时间为（），用动态规划算法所需的计算时间为（）。
正确答案: O(n*2n)；O(min{nc,2n})第15题：
关于0－1背包问题以下描述正确的是（）
- A、可以使用贪心算法找到最优解
- B、能找到多项式时间的有效算法
- C、使用教材介绍的动态规划方法可求解任意0－1背包问题
- D、对于同一背包与相同的物品，做背包问题取得的总价值一定大于等于做0－1背包问题
正确答案:D第16题：
用贪心算法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。
正确答案: 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
具体算法可描述如下：
void Knapsack（int n，float M，float v[]，float w[]，float x[]）
{Sort（n，v，w）；
int i；
for（i=1；i<=n；i++） x[i]=0；
float c=M；
for（i=1；i<=n；i++）
{if（w[i]>c） break；
x[i]=1；
c-=w[i]；
}
if（i<=n）x[i]=c/w[i]；
}第17题：
0-1背包问题的回溯算法所需的计算时间为（）
- A、O（n2n）
- B、O（nlogn）
- C、O（2n）
- D、O（n）
正确答案:A第18题：
关于背包加密算法的描述中，正确的是（）
- A、保证绝对安全
- B、物品总重量公开
- C、背包问题属于NP问题
- D、属于对称加密算法
- E、一次背包已不安全
正确答案:B,C,E第19题：
举反例证明0/1背包问题若使用的算法是按照pi/wi的非递减次序考虑选择的物品，即只要正在被考虑的物品装得进就装入背包，则此方法不一定能得到最优解（此题说明0/1背包问题与背包问题的不同）。
正确答案: 举例如：
p{7，4，4}，w={3，2，2}，c=4时，
由于7/3最大，
若按题目要求的方法，只能取第一个，收益是7。
而此实例的最大的收益应该是8，取第2，3 个。第20题：
问答题用贪心算法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。正确答案： 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。
具体算法可描述如下：
void Knapsack（int n，float M，float v[]，float w[]，float x[]）
{Sort（n，v，w）；
int i；
for（i=1；i<=n；i++） x[i]=0；
float c=M；
for（i=1；i<=n；i++）
{if（w[i]>c） break；
x[i]=1；
c-=w[i]；
}
if（i<=n）x[i]=c/w[i]；
}解析： 暂无解析第21题：
问答题有这样一类特殊0-1背包问题：可选物品重量越轻的物品价值越高。 n=6，c=20，P=（4，8，15，1，6，3），W=（5，3，2，10，4，8）。 其中n为物品个数，c为背包载重量，P表示物品的价值，W表示物品的重量。请问对于此0-1背包问题，应如何选择放进去的物品，才能使到放进背包的物品总价值最大，能获得的最大总价值多少？正确答案： 因为该0－1背包问题比较特殊，恰好重量越轻的物品价值越高，所以优先取重量轻的物品放进背包。最终可以把重量分别为2，3，4，5的三个物品放进背包，得到的价值和为15+8+6+4=33，为最大值。解析： 暂无解析第22题：
问答题一般背包问题的贪心算法可以获得最优解吗？物品的选择策略是什么？正确答案： 按照p[i]/w[i]≥p[i+1]/w[i+1]排序，选择当前利润/重量比最大的物品，可以获得最优解。解析： 暂无解析第23题：
问答题在0-1背包问题中，若各物品依重量递增序排列时，其价值恰好依递减序排列，对这个特殊的0-1背包问题，设计一个有效的算法找出最优解。（描述你的算法即可，无需证明算法的正确性）正确答案： 对于0－1背包问题本来是无法用贪心算法得到最优解的，但对于这类特殊的0－1背包问题，则可以用贪心算法去解。贪心策略如下：
首先将各物品依重量递增序（即也是价值递减序）排列，然后依照价值递减顺序选择物品装入背包，直到背包装不下下一件物品为止。
这里贪心算法的贪心选择策略是：每次总是选择价值最大（同时重量也最小）的物品，然后检查是否可以装入背包。解析： 暂无解析