背包问题之穷举解法

发表于 | 分类于 | |
字数统计: 1,077 | 阅读时长 ≈ 5

[0-1背包问题]有一个背包，背包容量是M=150kg。有7个物品，物品不可以分割成任意大小。（这句很重要）
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10 40 30 50 35 40 30

要想得到最优的结果，最容易想到的就是穷举法，那么首先用穷举法来处理这个问题。

首先就是要看穷举一共有多少种拿法，$2^7$种拿法，也就是说一共有128种方法，这里面一定有最优的，我们只要计算出128种拿法的价值，就一定能选出最优的拿法，当然要排除掉超过总容量的集合。

为了专业一点，首先要定义一个类Item来将问题转化为计算机能够理解的问题。

# item have three attribute: name,weight,value
class Item(object):
def __init__(self,n,v,w):
    self.name=n
    self.weight=float(w)
    self.value=float(v)

def getName(self):
    return self.name

def getValue(self):
    return self.value

def getWeight(self):
    return self.weight

def __str__(self):
    result = ' < '+self.name+' , '+str(self.value)+' , '+str(self.weight) + '>'
    return result

下面的这段算法提供了整个解空间，她的返回值就是整个$2^7$个集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#get the binary representation of a num n
def getBinaryRep(n,numDigitals):
    result=''
    while n>0:
        result=str(n%2)+result
        n=n//2
        
    if len(result)>numDigitals:
        raise ValueError("not enough digits")
    
    for i in range(numDigitals - len(result)):
        result = '0'+result
    return result
    
def genPowerSet(L):
    powerset=[]
    for i in range(2**len(L)):
        binstr = getBinaryRep(i,len(L))
        subset = []
        for j in range(len(L)):
            if binstr[j]=='1':
               subset.append(L[j])
        powerset.append(subset)
    return powerset

这段代码需要详细的解释一下。
getBinaryRep 就是获取一个数的指定位数的二进制表示。不足的位数补0，运行这个函数的结果如下所示：

1
2
print getBinaryRep(7,7)
0000111

genPowerSet 这个函数可以获取指定输入集合的所有子集合的表示。
原理如下：

我们可以把输入集合当做一个元素的列表，任意一个子集合看成是一个只包含了0,1的字符串，0表示不包含指定元素，1表示包含指定元素，那么全0就表示空集，全1就表示包括所有元素的集合（输入集合）。因此0—$2^7$所有的数的2进制就代表了输入集合的所有子集，也就是找到了问题的全部子空间。

函数的运行结果示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
L = ['A','B','C']
result = genPowerSet(L)
for i in range(len(result)):
    print result[i]

[]
['C']
['B']
['B', 'C']
['A']
['A', 'C']
['A', 'B']
['A', 'B', 'C']

准备工作做完了，下面来利用穷举法解决一下0/1背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Item import Item
import genPowerSet

def buildItem():
    names=['A','B','C','D','E','F','G']
    vals = [35,30,6,50,40,10,25]
    weights=[10,40,30,50,35,40,30]
    Items=[]
    for i in range(len(names)):
        Items.append(Item(names[i],vals[i],weights[i]))
    return Items

# Brute-force method
def chooseBest(pset,maxWeight,getVal,getWeight):
    bestVal = 0.0
    bestSet=None
    for items in pset:
        itemsVal=0.0
        itemsWeight=0.0
        for item in items:
            itemsVal +=getVal(item)
            itemsWeight +=getWeight(item)
            if itemsWeight <=maxWeight and itemsVal >bestVal:
                bestVal = itemsVal
                bestSet = items
    return (bestSet, bestVal)


def testBest(maxWeight=150):
    items = buildItem()
    pset = genPowerSet.genPowerSet(items)
    taken,val = chooseBest(pset,maxWeight,Item.getValue,Item.getWeight)
    print  'Total value of items taken = ',val
    for item in taken:
        print item
1
2
3
4
5
6
7
8
9
10
11
start1 = time.clock()
testBest()
end1=time.clock()
print "runing time is %f"  % (end1-start1)

Total value of items taken =  155.0
 < A , 35.0 , 10.0>
 < B , 30.0 , 40.0>
 < D , 50.0 , 50.0>
 < E , 40.0 , 35.0>
runing time is 0.001193

从实验结果上看，还是很快的，穷举法很完美啊。但是穷举的复杂度可是指数级的，当数据量比较大时就要歇了，举个例子，比如说集合的元素数目为20的时候，仅仅函数genPowerSet就要花费14.1231262126s,这就是指数的可怕，如果是26的话，就呵呵了（反正我是死机了）。

所以穷举法对于数据量小的情形是很好用的，但是数据量稍微大一些，就无路可走了。

显示 Gitment 评论