专栏首页蛮三刀的后端开发专栏01背包问题(动态规划)python实现

01背包问题(动态规划)python实现

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/littlethunder/article/details/26575417

在01背包问题中,在选择是否要把一个物品加到背包中,必须把该物品加进去的子问题的解与不取该物品的子问题的解进行比较,这种方式形成的问题导致了许多重叠子问题,使用动态规划来解决。n=5是物品的数量,c=10是书包能承受的重量,w=[2,2,6,5,4]是每个物品的重量,v=[6,3,5,4,6]是每个物品的价值,先把递归的定义写出来:

然后自底向上实现,代码如下:

def bag(n,c,w,v):
	res=[[-1 for j in range(c+1)] for i in range(n+1)]
	for j in range(c+1):
		res[0][j]=0
	for i in range(1,n+1):
		for j in range(1,c+1):
			res[i][j]=res[i-1][j]
			if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:
				res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
	return res

def show(n,c,w,res):
	print('最大价值为:',res[n][c])
	x=[False for i in range(n)]
	j=c
	for i in range(1,n+1):
		if res[i][j]>res[i-1][j]:
			x[i-1]=True
			j-=w[i-1]
	print('选择的物品为:')
	for i in range(n):
		if x[i]:
			print('第',i,'个,',end='')
	print('')

if __name__=='__main__':
	n=5
	c=10
	w=[2,2,6,5,4]
	v=[6,3,5,4,6]
	res=bag(n,c,w,v)
	show(n,c,w,res)

输出结果如下:

转载请注明:转自http://blog.csdn.net/littlethunder/article/details/26575417

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 动态规划——背包问题笔记

    给出程序:http://blog.csdn.net/littlethunder/article/details/26575417

    后端技术漫谈
  • [Leetcode][python]Generate Parentheses/括号生成

    后端技术漫谈
  • [Leetcode][python]Partition List/分隔链表

    给定一个链表以及一个目标值,把小于该目标值的所有节点都移至链表的前端,大于或等于目标值的节点移至链表的尾端,同时要保持这两部分在原先链表中的相对位置。

    后端技术漫谈
  • 动态规划——背包问题笔记

    给出程序:http://blog.csdn.net/littlethunder/article/details/26575417

    后端技术漫谈
  • 斐波纳耶数列

    斐波纳耶数列 <?php /** * for循环斐波纳耶 * * @param integer $n 数列长度 * @return array */...

    琯琯
  • Express4.x API (三):Response (译)

    Express4.x API 译文 系列文章 技术库更迭较快,很难使译文和官方的API保持同步,更何况更多的大神看英文和中文一样的流畅,不会花时间去翻译--,所...

    okaychen
  • 数据结构之动态规划问题

    数据结构中动态规划应该算得上是你避不开的一道槛了吧!其重要性不言而喻,今天就整理下学习笔记分享出来。希望对读者朋友也能有帮助,文章基本框架如下:

    小小詹同学
  • 【leetcode刷题】T62-罗马数字转整数

    例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做  XXVII, 即为 XX + V + II ...

    木又AI帮
  • 小程序体验版 新用户登录不了

    console.log(wx.getStorageSync("userInfo").id )

    用户6663311
  • 每日算法系列【LeetCode 556】下一个更大元素 III

    给定一个32位正整数 n,你需要找到最小的32位整数,其与 n 中存在的位数完全相同,并且其值大于n。如果不存在这样的32位整数,则返回-1。

    godweiyang

扫码关注云+社区

领取腾讯云代金券