利用python解决背包问题，清晰易懂

背包问题，大多数人应该都知道，但是知道如何解它的人却很少。在写这篇文章的时候，我在百度上搜索过这个问题的解法，可是…
在这里插入图片描述

我都点进去看了一下，然后，我什么玩意都没看懂。。。
于是我就自己思考，然后想出了一个比较简单的办法，虽然需要更多的代码，但是简单易懂。

1.采集数据

背包问题需要知道的数据有四个：背包容量，物品数量，物品重量以及所对应的价值。
前两个数据可以用普通变量来储存，后面两个则用单独的列表（一个列表对应一组数据），再把所得到的数据列表放在一个大的列表里。

u=[]
v=[]
s=int(input("背包容量："))
t=int(input("物品数量："))
for i in range(t):
    u.append(int(input(f"第{i+1}个物品重量：")))
    v.append(int(input(f"第{i+1}个物品价值：")))
a = []
for i in range(len(u)):
    q=[u[i],v[i]]
    a.append(q)

2.初步处理数据

此时得到的数据并不能直接用到后面的计算里面，需要进行一些处理，这时我的思路是这样的
把所有可能的情况都列出来，然后进行计算，把价值最大的选出来。
那么把可能的情况列出来，该如何做呢

from itertools import *
u=[]
v=[]
s=int(input())
t=int(input())
for i in range(t):
    u.append(int(input()))
    v.append(int(input()))
a=[]
for i in range(len(u)):
    q=[u[i],v[i]]
    a.append(q)

a=list(permutations(a))

al=[]
for i in a:
    al.append(list(i))

我用itertools里面的permutations函数把a，也就是装着所有物品的重量和对应价值的列表打乱，也就是列出来的每一种情况，这样之后再把函数创建出来的数组形式的数据打包成列表
此时，我脑子抽抽犯了一个巨大的错误：我把这数据拿来直接用了
什么意思呢，我把这些数据中的价钱直接加了起来，也就是说我计算出的是所有物品的总价值
然后，在我发觉不对劲，打印出来的数字怎么这么大的时候
我才意识到，我好像打印的是总价值
然后我把储存每一种情况所对应价值的列表打印了出来
一大片的同样的数字
然后我才想起来要把每组情况的重量处理成能装进背包的
怎么处理呢
现在，我已经得到了所有的排列组合，而把它们处理成背包可以装下的，就是把它们的重量减轻
于是，我抠出了这样的代码
`
gdl=[]
for x in al: # x是一种情况，示例：[[1(重量),2(价值)],[1(重量),2(价值)]]
jz = 0
wt = 0
jq = len(x)-1
for y in x: # y是一组数据，示例：[1(重量),2(价值)]

    jz+=y[1]
    wt+=y[0]
    
while True:
        
    if wt>s:
        wt -= x[jq][0]
        jz -= x[jq][1]
        jq -= 1

    if wt<=s:
        (jz)
        break

print(max(gdl))
`
先分别遍历每一组数据，然后把它们的价值和重量分别用变量保存，
用变量（jq）来储存要去掉的重量所对应的那一组数据，在后面的死循环中把重量和价值一步步减轻，直到重量小于/等于背包容量
利用变量（gdl）来储存得出的每一组处理出来的可以装进背包的物品的总价值，具体是怎么做的这个代码应该是个会python的都看得懂
在最后我把所有的代码展示出来，供大家参考

from itertools import *
u = []
v = []
s = int(input("背包容量："))
t = int(input("物品数量："))
for i in range(t):
    u.append(int(input(f"第{i+1}个物品重量：")))
    v.append(int(input(f"第{i+1}个物品价值：")))
a = []
for i in range(len(u)):
    q = [u[i], v[i]]
    a.append(q)

a=list(permutations(a))

al=[]
for i in a:
    al.append(list(i))
    

gdl=[]
for x in al:  # x是一种情况，示例：[[1(重量),2(价值)],[1(重量),2(价值)]]
    jz = 0
    wt = 0
    jq = len(x)-1
    for y in x:  # y是一组数据，示例：[1(重量),2(价值)]
        
        jz+=y[1]
        wt+=y[0]
        
    while True:
            
        if wt>s:
            wt -= x[jq][0]
            jz -= x[jq][1]
            jq -= 1

        if wt<=s:
            gdl.append(jz)
            break

print(max(gdl))

秒客网

利用python解决背包问题，清晰易懂

1.采集数据

2.初步处理数据

相关文章