当前位置: 代码迷 >> 综合 >> 动态规划--(01背包 poj3624 )
  详细解决方案

动态规划--(01背包 poj3624 )

热度:97   发布时间:2023-12-08 19:11:38.0

关于背包问题:

众所皆知,这里讲给出关于背包问题的一些简介:

一个旅行者准备随身携带一个背包. 可以放入背包的物品有n , 每种物品的重量和价值分别为 wj , vj . 如果背包的最大重量限制是 b, 怎样选择放入背包的物品以使得背包的价值最大

题目就是这么简单:

先思考一个问题:就是每种物品可以重复选择,这种要怎么解决:

Fk(y):装前 k 种物品, 总重不超过 y, 背包的最大价值;

这里的子问题:很好理解,想一想,每一次你要去拿物品,你会想,