Python

Python

Python_背包问题蛮力法解决（采用bin函数辅助生成集合子集）（bin函数实现）【2021-11-24】

• 1.bgwt.py
• 2.结果示例
• • • 物品5个，负重12
    • 物品5个，负重15
    • 物品6个，负重15

1.bgwt.py

import os
w = []
v = []
n = eval(input("输入物品个数："))
sw = eval(input("输入背包负重："))

for i in range(n):
    tw = eval(input("输入重量："))
    w.append(tw)
    tv = eval(input("输入价值："))
    v.append(tv)

bnum = list(bin(2**n-1))
bnum.pop(0)
bnum.pop(0)
# 上面是在列表中删除0b两个字符，只保留二进制

bitn = len(bnum)
#print(bnum)
#print(bitn)
ls = []

for i in range(2**n):
    tb = list(bin(i))
    tb.pop(0)
    tb.pop(0)
    #print(tb)
    ttb = []
    for j in range(len(tb)):
        ttb.append(eval(tb[j]))
    
    tb = ttb
    #print(tb)
    lentb = len(tb)
    for k in range(bitn - lentb):
        tb.insert(0,0)
    ls.append(tb)   #将每次生成的子集添加到ls子集集合列表中

print("全部子集如下：")
for i in range(2**n):
    print(ls[i])

flag = -1
maxvalue = 0
goodweight = 0

for i in range(2**n):
    tweight = 0
    tvalue = 0
    for j in range(n):
        if tweight >= sw:
            tweight = 0
            tvalue = 0
            break;
        elif ls[i][j] == 1:
            tweight = tweight + w[j]
            tvalue = tvalue + v[j]
    
    if maxvalue < tvalue and tweight <= sw:
        goodweight = tweight
        maxvalue = tvalue
        flag = i
#上面是获得最佳集合，即最大价值且重量不超过背包负重
#print(sw)

print("重量与对应价值：")
print(w)
print(v)
print("最好组合0/1为：")
print(ls[flag])
print("最佳重量：{0}".format(goodweight))
print("最高价值：{0}".format(maxvalue))

os.system("pause")

2.结果示例 物品5个，负重12

物品5个，负重15

物品6个，负重15