拖延症重症患者 2017-04-30 10:55 采纳率: 33.3%
浏览 1319

poj 1267 01背包之后为什么还需要求一遍最大值?

题目描述
Nanae把饥肠辘辘的josnch带去一家自助餐厅,面对面前眼花缭乱的美味josnch呆住了。

假设有N种食物,每种食物只有一样,而且每种食物有对应的体积Wi (1 <= Wi <= 400),食用每一种食物都能增加对应的愉悦值Di(1 <= Di <= 100).

现在已知josnch肚子的容量为M(1 <= M <= 12,880),现在假设josnch足够聪明,请问他如何选择能在可接受的范围内达到愉悦值最大。

输入
第一行输入两个整数,N和M。

第二行到第N+1行输入每行两个整数,Wi 和 Di ,分别代表 第i件物品的体积和所能带来的愉悦值。

输出
输出一个整数,也就是在最佳选择下的愉悦值。

样例输入
4 6
1 4
2 6
3 12
2 7
样例输出
23

  • 写回答

1条回答 默认 最新

  • 白杨白杨白杨 2017-04-30 11:44
    关注

    f[i][v]表示前i件物品**恰**放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:
    f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }
    f[v]有意义当且仅当存在一个前i件物品的子集,其费用总和为f[v]。所以按照这个方程递推完毕后,最终的答案并不一定是f[N] [V],而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉,在转移方程中就要再加入一项f[v-1],这样就可以保证f[N] [V]就是最后的答案。
    来自百度百科
    http://baike.baidu.com/link?url=hAw3Nr8HMPc6-PQPIBX1F-1jADC601RhaCRY9GweYCICTHl0a6LAuAB2qQ63essWRxLLikimiU2-2uPvdqNI9D5zCL6HtE8NnK3ZLEQj0kBE7hqBuSJQqQIktkgvsy-_

    评论

报告相同问题?

悬赏问题

  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题