转载

经典背包问题的探讨

一、背包问题的描述

背包问题可以有多种形式,下面将对其逐一进行描述:

(1)经典的0-1背包问题(无物品的价值):

假设有一个能装入容量为C的背包和n件重量分别为w1,w2,,...,wn的物品,能否从n件物品中挑选若干件恰好装满背包,要求找出所有满足上述条件的解。

当C=10,各件物品重量为{1,8,4,3,5,2}时,可以找到下列4组解:(1,4,3,2)、(1,4,5)、(8,2)和(3,5,2)。

根据这个问题的一个变形是:

已知一个数为C,一个长度为n的无序的数组,分别是数w1,w2,...,wn,能否从这n个数中找到若干个数使其和等于数C,要求找出所有满足上述条件的解。

(2)经典的0-1背包问题(有物品的价值):

给定n种物品和一个背包。物品i的重量是wi,其价值为vi,背包的容量为C。应该如何选择装入背包中的物品,使得装入背包中物品的总价值最大?

上面的两个问题都是0-1背包问题,因为隐含的信息是:对每种物品只有两种选择,即装入背包或者不装入背包。不能将物品装入多次,也不能只装入部分的物品。

(3)背包问题:与0-1背包问题类似,所不同的是在选择物品i装入背包时,可以选择物品i的一部分,而不一定要全部装入背包。

二、解决思路

对于问题(1),本文采用的是回溯思想,利用栈的“后进先出”的特性 ,首先将物品排成一列,然后顺序选取物品装入背包,假设已选取了前i件物品之后背包还没装满,

则继续选取第i+1件物品,若选该件物品的重量太大不能装入,则放弃而继续选取下一件,直至背包装满为止。但是如果在剩余物品中找不到合适的物品以填满背包,则说明

“刚刚”装入背包的那件物品“不合适”,应该将它取出,再继续从它之后的物品中选取,如此重复,直至求得满足要求的解,或者无解为止。因为回溯的规则也是“后进先出”,

所以采用栈这个数据结构。

对于问题(2),其实可以采用问题(1)的解法 ,因为要使价值最大化,肯定也是尽可能多的往背包里装物品。只是此时不要求装满背包,而是在过程中不断比较每种情况的

总价值,并找到总价值最大的选择方式。

对于问题(3),这种背包问题可以用贪心算法求解 ,先计算每种物品单位重量的价值vi/wi;然后根据贪心策略,将可能多得单位重量价值最高的物品装入背包;依次使用这种

策略,直至装满背包为止。

三、程序设计

问题(1):

经典背包问题的探讨

经典背包问题的探讨

问题(2):

经典背包问题的探讨

经典背包问题的探讨

问题(3):

经典背包问题的探讨

经典背包问题的探讨

正文到此结束
Loading...