shuwei81
2022-04-16 13:24
采纳率: 33.3%
浏览 269

数据结构中背包问题如何避免递归算法迭代到重复一样的数

问题遇到的现象和发生背景

img


题干如上,我现在的一个问题是我不知道如何能保证迭代算法每次迭代数都是不重复的,比如目前的代码算出来的最优解是value 8 8 8 8 36 ,weight为4的宝物用了四次 但市这明显不对的,宝物只有一个。如何能保证迭代出来的数字都不一样 ,按照题目字面意思来说 即每个宝物如果他们在最优解中出现,他们只能出现一次呢?
第二个 我现在箱求出最优解的组合 那我应该怎么做呢?

问题相关代码,请勿粘贴截图
def recDCCC(weightlist,maxweight,num,valuelist,value,l,p,k):
    ok=[]
    if num==4:
        print('stop1')
        return value ##递归结束条件 并开始新的一轮递归
    if maxweight<=0:
        print('stop2')
        return value
    ###op.append([val for val in ok if val not in weightlist])##将OK表中不属于valuelist的元素,重复元素剔除出来,除非重复是8,发生重复,立即结束
    else:
        for i in range(0,5): 
                    ok.append(valuelist[i])
                    print(valuelist[i])
                    print(ok)
                    numcoins=recDCCC(list(set(weightlist)-set([weightlist[i]])) ,maxweight-weightlist[i],num+1,list(set(valuelist)-set([valuelist[i]])) ,value+valuelist[i],l,p,k)
                    weightlist=p
                    valuelist=k
                    print(numcoins)
                    print('break')
                    if l<numcoins:
                            l=numcoins
                            print('end')
                    else:
                            l=l
                    
    return l

print(recDCCC([2,3,4,5,9],20,0,[3,4,8,8,10],0,0,[2,3,4,5,9],[3,4,8,8,10]))
运行结果及报错内容

【8,8,8,8】 最大值36 但这个明显不对 应该为29 每个宝物只能最多出现一次

我的解答思路和尝试过的方法
我想要达到的结果
  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

12条回答 默认 最新

相关推荐 更多相似问题