shuwei81 2022-04-16 13:24 采纳率: 50%
浏览 299
已结题

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

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

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条回答

      报告相同问题?

      相关推荐 更多相似问题

      问题事件

      • 系统已结题 4月25日
      • 已采纳回答 4月17日
      • 修改了问题 4月16日
      • 赞助了问题酬金140元 4月16日
      • 展开全部

      悬赏问题

      • ¥15 edge浏览器最近莫名其妙老是每隔一段时间弹出色情网站,求解决。。
      • ¥15 “glmnet”运行出错
      • ¥30 如何用matlab表达以下公式?
      • ¥15 在arm架构芯片上基于32位linux操作系统做内存检查
      • ¥15 怎么样才能禁止VS自动调整Windows窗体布局
      • ¥15 mysql5.7.40安装到Initializing database报错,如何解决?
      • ¥30 如何降低hdfs中datanode的JVM内存用量
      • ¥15 Android URL如何转成视频/音频,可行吗?
      • ¥20 Hive SQL数据查询,子查询
      • ¥15 c++字符串分割问题