python 递归解决 背包问题

决策过程如下

  1. 每次考虑一个背包是否放下，从第一个到最后一个
  2. 比较放这个和后面的，不放这个和后面的效益哪个高

决策树

代码

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Jilu(float):
    # 实现float型与list合并在一起，所有float方法都可用
    def __new__(cls,value,jilu):
        o=super(Jilu,cls).__new__(cls,value)
        if type(jilu) is not list:
            o.jilu=[jilu]
        else:
            o.jilu=jilu
        return o
    def __add__(self,jl):
        a=self.__float__()+jl
        if type(self)==type(jl):
            tp=self.jilu=self.jilu+jl.jilu
        else:
            tp=self.jilu
        return self.__new__(Jilu,a,self.jilu)
    def __str__(self):
        t1=self.__float__()
        t2=self.jilu
        return "value:{0},jilu:{1}".format(t1,t2)

class jc():
    # 决策
    def __init__(self,bb:list):
        # self.bb=sorted(bb,key=lambda x:x.weight,reverse=1)
        self.bb=bb
    def dg(self,n=0,wt=0):
        # 当前考虑的 剩余质量
        # 放入或者不放入
        # 假设只剩下背包，看能不能放下
        # 决策过程
        # 比较放这个和后面的，不放这个和后面的效益哪个高
        if n>=self.bb.__len__():
            return Jilu(0,'')
        # 返回的要为value
        if wt<self.bb[n][0]:#放不下
            t1=-1
            t2=self.dg(n+1,wt)#不放这个
            pass
        if wt>=self.bb[n][0]:#能放下
            t1=Jilu(self.bb[n][1],str(n))+self.dg(n+1,wt-self.bb[n][0])#放下这个
            t2=self.dg(n+1,wt)#不放这个
            pass
        return max(t1,t2)


bb=[(2,2),(2.5,3),(4,5),(5,8),(1,2),(3,4),(3,4)]
#背包的记录 第一个数是质量，第二个是价值
a=jc(bb)
print(a.dg(wt=10))