首页 > 代码库 > 0 1背包问题 (内有题目列表)
0 1背包问题 (内有题目列表)
问题描述:一个背包可承重W,现有n件东西,东西 i 的价值为 vi,重量为wi。现在从这n件东西中拿出几件装到背包中,问可获得的最大价值?
举例:W = 3, n = 3;
东西的价值
vi wi
3 4
4 5
5 6
DP的解法:
先从递归的角度理解这个问题,然后在贴上非递归的模板。
现在为东西编号:0 1 2 3 …n-1;我们先从n-1开始(其实从哪一端开始都无所谓,不要在意这些细节),我其实不觉得这个算法属于DP的,不管这个了。
Make(i,j) = max{Make(i-1,j-w[i])+v[i](取编号为 i 的东西),Make(i-1,j)(没有取编号为i的产品)}
0 1背包问题 (内有题目列表)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。