数据结构中背包问题如何避免递归算法迭代到重复一样的数
问题遇到的现象和发生背景
题干如上，我现在的一个问题是我不知道如何能保证迭代算法每次迭代数都是不重复的，比如目前的代码算出来的最优解是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 每个宝物只能最多出现一次
我的解答思路和尝试过的方法
我想要达到的结果
折腾了好半天，整理出一种实现方法，貌似是可行的，目前测试是没问题的，你参考一下：
基本思路是就是先考虑全拿走，发现负重超了，那就依次尝试丢弃一个，直到负重不超，这时剩下的列表做为备选列表，循环完以后，在所有备选列表中找最优解
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}")
如有帮助，请采纳。
#!/usr/bin/python
# -*- coding: UTF-8 -*-
"""
@author: Roc-xb
"""
"""
n :物品的数量，
c:书包能承受的重量，
w : 每个物品的重量，
v :每个物品的价值
"""
def bag(n, c, w, v):
# 置零，表示初始状态
value = [[0 for j in range(c + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, c + 1):
value[i][j] = value[i - 1][j]
# 背包总容量够放当前物体，遍历前一个状态考虑是否置换
if j >= w[i - 1] and value[i][j] < value[i - 1][j - w[i - 1]] + v[i - 1]:
value[i][j] = value[i - 1][j - w[i - 1]] + v[i - 1]
for x in value:
print(x)
return value
def show(n, c, w, value):
print('最大价值为:', value[n][c])
x = [False for i in range(n)]
j = c
for i in range(n, 0, -1):
if value[i][j] > value[i - 1][j]:
x[i - 1] = True
j -= w[i - 1]
print('背包中所装物品为:')
for i in range(n):
if x[i]:
print('第', i + 1, '个,', end='')
if __name__ == '__main__':
n = 5
c = 20
w = [2, 3, 4, 5, 9]
v = [3, 4, 8, 8, 10]
value = bag(n, c, w, v)
show(n, c, w, value)
把已选择的从列表中剔除
# 宝物重量及价值
treasure = [{'w':2,'v':3},{'w':3,'v':4},{'w':4,'v':8},{'w':5,'v':8},{'w':9,'v':10}]
# 大盗最大承重和可能拿走的宝物最多件数
max_w, max_num = 20, len(treasure)
# 初始化maxvalue和treasure_used，记录在当前可选宝物范围中，大盗可拿走的最大总价值及对应宝物
mtv = [[0 for i in range(max_w+1)] for j in range(max_num+1)]
treasure_used= [[False for p in range(max_w+1)] for q in range(max_num+1)]
# 循环添加宝物至“大盗可选清单”
for i in range(1,max_num+1):
need_w,get_v = treasure[i-1]['w'],treasure[i-1]['v'] # 添加的宝物的重量和价值
for j in range(1,max_w+1):
if i==1: # 若是清单只有一件宝物
if j<need_w: # 若是当前物品重量大于背包容量
mtv[1][j]=0
else: # 若是当前物品可放入背包
mtv[1][j]=get_v
treasure_used[1][j] = True
else:
if j<need_w: # 若是当前物品重量大于背包容量
mtv[i][j]=mtv[i-1][j] # 和这个物品不存在时同样
else:
# 若是能够放，须要进一步决策：大于上一次选择的最佳方案则更新mtv[i][j]
treasure_used[i][j] = mtv[i - 1][j - need_w] + get_v> mtv[i - 1][j]
mtv[i][j]=max(mtv[i-1][j-need_w]+ get_v ,mtv[i-1][j])
# 记录在mtv[i][j]时是否选择了放入第i-1件宝物
print(mtv[max_num][max_w]) # 回溯打印编号
num=max_num
w=max_w
s = ""
while num > 0:
if treasure_used[num][w]:
s=s+str(num-1)+" " # 减一是由于宝物序号是从零开始的
w = w - treasure[num-1]['w']
num = num - 1 # 处理依据 mtv[i-1][j-need_w]+ get_v
else:
num = num - 1 # 处理依据 mtv[i-1][j]
print(s)
如有用请采纳
可考虑借助itertools中combination方法
from itertools import combinations # 生成组合数
weightlist = [2, 3, 4, 5, 9]
valuelist = [3, 4, 8, 8, 10]
maxweight = 20
resultlist = []
def func(i: int) -> list:
'''
从给定样本中挑选i件(排列组合中的组合),计算其重量是否在限制内,
若有,将其添加至暂存列表中,i加一;否则停止迭代。以此递归
'''
global resultlist
state = False
for c in combinations(range(len(weightlist)), i):
totalweight = sum(weightlist[j] for j in c)
if totalweight <= maxweight:
state = True
valueselected = [valuelist[j] for j in c]
totalvalue = sum(valueselected)
resultlist.append([totalvalue, valueselected])
if state:
func(i + 1)
func(1)
print(max(resultlist)) # [29, [3, 8, 8, 10]]
用一个标志位数组flag=[0 , 0, 0, 0]
迭代过某一个数之后，把对应的flag位置的数组变成1，下一次迭代的时候先看是不是1，是1就不选择此数去迭代
望采纳
题主的问题就是经典的0-1背包，在于实现拿去物品不超过重量的的最大价值，对于一件物品，选择拿（1）与不拿（0）。
这里我帮你实现了最经典的解决方法，算法在于动态规划这个过程以及这个过程的选择。
实现这个算法花的时间比较多，如有帮助，希望采纳哦，有问题也可以提出
结果如下：
"""
encoding: utf-8
@author: Charzous
@license: Copyright © 2021 Charzous
@software: Pycharm
@file: Knapsack_problem.py
@time: 2022-04-16
"""
# 因为算法实现从下标1计数，所以0下标None填充
weight = [None, 2, 3, 4, 5, 9]
value = [None, 3, 4, 8, 8, 10]
take = [None, 0, 0, 0, 0, 0] # 标记物品是否拿走
m = [] # 动态规划自底向上保存的局部最优解
for i in range(6):
m.append([])
for j in range(21):
m[i].append(0)
# print(m[2][5])
def knapsack(v, w, c, n):
jM = min(w[n] - 1, c)
# print(jM)
# 填最底层，列标j表示当前背包容量
for j in range(1, jM + 1):
m[n][j] = 0
for j in range(w[n], c + 1):
m[n][j] = v[n]
# 自底向上
for i in range(n - 1, 1, -1):
jM = min(w[i] - 1, c)
for j in range(1, jM + 1):
m[i][j] = m[i + 1][j]
for j in range(w[i], c + 1): # 在背包容量允许情况下，选择是否加入物品 i，得到更大的价值
m[i][j] = max(m[i + 1][j], m[i + 1][j - w[i]] + v[i])
# 只需要填最右上角，通过比较m[2][c]、当前能够放入v[1]
# 后剩下容量放入物品的价值之和，取最大者就是最大价值
m[1][c] = m[2][c]
if c >= w[1]:
m[1][c] = max(m[1][c], m[2][c - w[1]] + v[1])
def traceback(c, n):
for i in range(1, n):
if m[i][c] == m[i + 1][c]:
take[i] = 0
else:
take[i] = 1
c -= weight[i]
if m[n][c] > 0:
take[n] = 1
else:
take[n] = 0
if __name__ == '__main__':
knapsack(value, weight, 20, 5)
traceback(20, 5)
for l in m:
print(l)
print(f'最大值：{m[1][20]}')
print(f'选取的物品：{[i for i in range(6) if take[i] == 1]}')
拿到最优解的同时求出最优解的组合
import copy
# 用一个字典来保存宝物的重量w和价值v
tr = {(2, 3), (3, 4), (4, 8), (5, 8), (9, 10)}
# 设置背包最大承重
max_w = 20
# 初始化记忆化表格m
# key是(宝物组合，最大重量)，value是最大价值和组合
m = {}
def thief(tr, w):
if tr == set() or w == 0: # 基本结束条件
m[(tuple(tr), w)] = [0, set()]
return m[(tuple(tr), w)]
elif (tuple(tr), w) in m:
return m[(tuple(tr), w)]
else:
vmax = 0
th = set()
for t in tr:
if t[0] <= w:
# 逐个从集合中去掉某个宝物t，递归调用
# 选出所有价值中的最大值
v = thief(tr - {t}, w - t[0])[0] + t[1] # 调用自身
if v > vmax:
vmax = v
th = copy.deepcopy(m[(tuple(tr - {t}), w - t[0])][1])
th.add(t)
m[(tuple(tr), w)] = [vmax, th]
return vmax, th
# 输出结果
res = thief(tr, max_w)
print(res)
解决背包的函数的完整代码如下
你的问题是递归里面包含返回OK列表，等于每次递归都会执行 ok=[]。
def recDCCC(W, wt, val):
n=len(val)
table = [[0 for x in range(W + 1)] for x in range(n + 1)]
for i in range(n + 1):
for j in range(W + 1):
if i == 0 or j == 0:
table[i][j] = 0
elif wt[i-1] <= j:
table[i][j] = max(val[i-1] + table[i-1][j-wt[i-1]], table[i-1][j])
else:
table[i][j] = table[i-1][j]
return table[n][W]
val = [3,4,8,8,10]
wt = [2,3,4,5,9]
W = 20
print(recDCCC(W, wt, val))
递归
def recDCCC(W, wt, val, n):
if n == 0 or W == 0:
return 0
if (wt[n-1] > W):
return recDCCC(W, wt, val, n-1)
else:
return max(
val[n-1] + recDCCC(
W-wt[n-1], wt, val, n-1),
recDCCC(W, wt, val, n-1))
val = [3,4,8,8,10]
wt = [2,3,4,5,9]
W = 20
n = len(val)
print(recDCCC(W, wt, val, n))
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632
自己搜一下就有了
https://blog.csdn.net/weixin_43412569/article/details/104856486
