首页 > 其他 > 详细

第五讲 二维费用的背包问题(粗糙,勿点)

时间:2018-11-27 20:11:16      阅读:164      评论:0      收藏:0      [点我收藏+]

对背包九讲的学习:网址

题目:

二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值(两种背包容量)分别为V和U。物品的价值为w[i]。

 

状态转移方程:

f[i][v][u]=max{f[i-1][v][u],f[i-1][v-a[i]][u-b[i]]+w[i]}

加一个维度而已

 

最后在f[0..V][0..M]范围内寻找答案。

 

第五讲 二维费用的背包问题(粗糙,勿点)

原文:https://www.cnblogs.com/zyacmer/p/10028560.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!