TJJJJJJJJJJ
TJJJJJJJJJJ
2020-10-10 17:33
采纳率: 60%
浏览 131

小白搞不懂回溯啊 求大佬指教

问题是这样的:
有一个行李箱
给出最多能装_多少kg__的限制(w_limit)
,又给了一个货物利润的array1和对应货物重量的array2
,要求output利润的最大值

然后这是我写的代码

def subset(S,sub,array1,array2,n,d):
    m=0
    if len(S) == 0:
        pft_sum=0
        wgt_sum=0
        for i in sub:
            pft_sum += array1[i]
            wgt_sum += array2[i]
            if wgt_sum <= n:
                if pft_sum > m:
                    m = pft_sum
        return 
    subset(S[1:],sub,array1,array2,n,d)
    subset(S[1:],sub+[S[0]],array1,array2,n,d)
    return m






w_limit=25
wgt=[2, 8, 5, 6, 15, 3, 7]
pft=[30, 100, 10, 120, 280, 50, 40]

S=[]
for i in range(len(wgt)):
    S.append(i)


d=subset(S,[],pft,wgt,w_limit,[])
print(d)

但是这样子算出来的d一直是0,是因为输出的m每一个回溯都会=0一下吗
求解!

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

2条回答 默认 最新

  • w15059001146
    忧王 2020-10-12 11:22
    已采纳

    图片说明
    基本功啊基本功
    首先告诉我你的参数d是干嘛用的? 是没用的
    然后我明白你是想每次都用当前的利润总和与当前最大利润对比,但是你仔细看看,每次比较,当前最大利润都是m = 0,这还有比较的必要吗?
    为什么是这样呢?因为你没有把每次计算好的m传递出来,回溯什么的不明白就自己拿笔把每一次的结果都写出来,多练多写
    好了回到正题,既然要保持一个最大利润参数作为每次比较的依据,你得把它传递出来!
    图片说明
    代码结构我就不动了,增加一个m参数传递
    结果你自己看看对不对,第一个return是为了em.回溯的参数传递,第二个return传出最终结果
    图片说明

    点赞 评论
  • qq_39412061
    吃鸡王者 2020-10-12 11:06
    def subset(S,sub,array1,array2,n,d):
        global m
        if len(S) == 0:
            pft_sum=0
            wgt_sum=0
            for i in sub:
                pft_sum += array1[i]
                wgt_sum += array2[i]
                if wgt_sum <= n:
                    if pft_sum > m:
                        m = pft_sum
            return 
        subset(S[1:],sub,array1,array2,n,d)
        subset(S[1:],sub+[S[0]],array1,array2,n,d)
    
    
    
    
    
    
    w_limit=25
    wgt=[2, 8, 5, 6, 15, 3, 7]
    pft=[30, 100, 10, 120, 280, 50, 40]
    
    S=[]
    for i in range(len(wgt)):
        S.append(i)
    
    
    subset(S,[],pft,wgt,w_limit,[])
    print(m)
    
    

    这样修改就好了。还有一个建议,就是这种背包问题建议使用动态规划来做,思路会更清晰一点。

    点赞 评论

相关推荐