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

Question

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

题干如上，我现在的一个问题是我不知道如何能保证迭代算法每次迭代数都是不重复的，比如目前的代码算出来的最优解是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 每个宝物只能最多出现一次

我的解答思路和尝试过的方法

我想要达到的结果

Answer 1

折腾了好半天，整理出一种实现方法，貌似是可行的，目前测试是没问题的，你参考一下：
基本思路是就是先考虑全拿走，发现负重超了，那就依次尝试丢弃一个，直到负重不超，这时剩下的列表做为备选列表，循环完以后，在所有备选列表中找最优解

def fun(lst,weight,value, max_weight,lsts, ws, vs):
    w_total = sum([weight[i] for i in lst]) #计算当前备选列表中的总重量
    v_total = sum([value[i] for i in lst])  #计算当前备选列表中的总价值
    if w_total>max_weight: #总重量超过最大负重则进行减负
        for i in lst:  #遍历当前宝物列表
            c = [x for x in lst] #复制列表，防止改变lst
            c.remove(i) #移除一个宝物
            fun(c,weight,value,max_weight,lsts, ws, vs) #递归计算移除宝物后的各种参数
    else:                 #总重量不大于最大负重，记录当前宝物列表
        if lst not in lsts:  #判断列表是否重复，重复不记录
            lsts.append(lst)
            ws.append(w_total)
            vs.append(v_total)

lst = [0,1,2,3,4]     #宝物编号列表
weight = [2,3,4,5,9]  #宝物重量
value = [3,4,8,8,10]  #宝物价值
max_weight = 20  #最大负重
lsts = [] #可能性列表
ws = [] #对应可能性列表的宝物总重量
vs = [] #对应可能性列表的宝物总价值
fun(lst,weight,value,max_weight,lsts, ws, vs)
for i in range(len(lsts)):
    print(f"{ws[i]},{vs[i]},{lsts[i]}")
max_value = vs[ws.index(max(ws))]
print(f"能带走的最大价值为：{max_value}")

如有帮助，请采纳。