DDR爱好者之家

浅析python实现动态规划背包问题
站长资源 2024/11/24 佚名
40 1538
DDR爱好者之家 Design By 杰米

一个包可以背4kg的东西，现在有四件东西，重量分别为1kg，4kg，3kg，1kg，价值为：1500,3000,2000,2000；

现在要求你，在包里背的东西价值最大，但是不能超过背包的最大载重量

#几件物品的重量
w = [0,1,4,3,1]
#几件物品的价值
v= [0, 1500, 3000, 2000, 2000]
#物品数量
n = len(w) - 1
#包的载重量
m = 4
 
#建立一个列表表示在包中的物品，元素是True时代表对应元素放入
x = [] 
#放入包中的总价值
value = 0
#建立一个矩阵，来表示在前i个物品中，当载重量是j时，放入包中的最大价值，table[i][j]
table = [[0 for i in range(m+1)] for j in range(n+1)]
 
def dynamic(w,v,n,m,x):
 #计算table矩阵
 for i in range(1, n+1): #代表物品一件一件的考虑
  for j in range(1, m+1):  #代表子背包的大小一点一点的考虑
   if (j >= w[i]): #当背包的大小大于物品的重量时，考虑放进去
    table[i][j] = max(table[i-1][j], table[i-1][j-w[i]] + v[i])
   else:
    table[i][j] = table[i -1][j] #如果放不进去，就继承之前的价值
    
 #递推装入背包中的物体，寻找跳变的地方，从最后结果开始逆推
 j = m
 for i in range(n, 0, -1):
  if table[i][j] > table[i- 1][j]: #如果多加一件物品之后，价值增大，就将这一件物品加入列表中
   x.append(i)
   j = j - w[i] #此时为剩余背包的载重量
   
 #返回最大价值，即表格中最后一行最后一列的值
 value = table[n][m]
 return value
 
print("最大价值为：", str(dynamic(w, v, n, m, x)))
print("物品的索引：", x)

PS：python动态规划之背包问题

import numpy as np
def bag(weight,values,weight_cont):
 num = len(weight)
 weight.insert(0,0)
 values.insert(0,0)
 bag = np.zeros((num+1,weight_cont+1),dtype=np.int)
 for i in range(1,num+1):
  for j in range(1,weight_cont+1):
   if j >= weight[i]:
    bag[i][j] = max(bag[i-1][j],bag[i-1][j-weight[i]]+values[i])
   else:
    bag[i][j] = bag[i][j-1]
 return bag[-1][-1]
if __name__ == '__main__':
 weight = [1, 2, 4, 10, 12]
 values = [1200, 1500, 2000, 1300, 2500]
 weight_cont = 20
 re = bag(weight,values,weight_cont)
 print(re)
DDR爱好者之家 Design By 杰米
广告合作：本站广告合作请联系QQ：858582 申请时备注：广告合作（否则不回）
免责声明：本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除！
DDR爱好者之家 Design By 杰米
ddrfans.com DDR爱好者之家
8,675无损音乐
1,324高清电影
213破解软件
70,141收录资讯

《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线

暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。

艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。

《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。

更新日志

友情链接

杰晶网络 DDR爱好者之家 南强小屋 黑松山资源网 白云城资源网
DDR爱好者之家 Design By 杰米