python背包问题
背包问题可以分为:01背包 和 完全背包问题。简要概括:01背包:每种物品只能拿一次或者不拿。完全背包:每种物品可以拿无限次。01背包:import numpy as npweight=[1,3,6,5,7]#物品重量price=[2,1,3,5,4]#物品价值weight_most=10def fullbag(weight,price,weight_most):#return max value
·
背包问题可以分为:01背包 和 完全背包问题。
简要概括:
01背包:每种物品只能拿一次或者不拿。
完全背包:每种物品可以拿无限次。
01背包:
import numpy as np
weight=[1,3,6,5,7] #物品重量
price=[2,1,3,5,4] #物品价值
weight_most=10
def fullbag(weight,price,weight_most):#return max value
num = len(weight) #获取物品总量
weight.insert(0,0) #不存在第0个物品,故插入一个0
price.insert(0,0) #同上
bag=np.zeros((num+1,weight_most+1),dtype=np.int32)#使用numpy快速建立数组,下标从零开始
# bag0 = [0 for j in range(weight_most+1)] #不导入np三方库
# bag = [bag0 for i in range(num+1)]
for i in range(1,num+1): #这俩循环的取值为行与列,每件物品进行循环
for j in range(1,weight_most+1): #从轻的开始拿
if weight[i]<=j:
bag[i][j]=max(bag[i-1][j-weight[i]]+price[i],bag[i-1][j])
else:
bag[i][j]=bag[i-1][j]
print(bag)
return bag[-1,-1]
result=fullbag(weight,price,weight_most)
print(result)
解法来源:https://blog.csdn.net/your_answer/article/details/79274789
完全背包:
import numpy as np
weight=[1,3,6,5,7] #物品重量
price=[2,1,3,5,4] #物品价值
weight_most=10
def fullbag(weight,price,weight_most):#return max value
num = len(weight) #获取物品总量
weight.insert(0,0) #不存在第0个物品,故插入一个0
price.insert(0,0) #同上
bag=np.zeros((num+1,weight_most+1),dtype=np.int32)#使用numpy快速建立数组,下标从零开始
# bag0 = [0 for j in range(weight_most+1)] #不导入np三方库
# bag = [bag0 for i in range(num+1)]
for i in range(1,num+1): #这俩循环的取值为行与列,每件物品进行循环
for j in range(1,weight_most+1): #从轻的开始拿
if weight[i]<=j:
bag[i][j]=max(bag[i-1][j-weight[i-1]]+price[i-1],bag[i-1][j])
else:
bag[i][j]=bag[i-1][j]
print(bag)
return bag[-1,-1]
result=fullbag(weight,price,weight_most)
print(result)
该博主为完全背包提供了更多的解法:
更多推荐
已为社区贡献3条内容
所有评论(0)