关于背包问题:
众所皆知,这里讲给出关于背包问题的一些简介:
一个旅行者准备随身携带一个背包. 可以放入背包的物品有n 种, 每种物品的重量和价值分别为 wj , vj . 如果背包的最大重量限制是 b, 怎样选择放入背包的物品以使得背包的价值最大?
先思考一个问题:就是每种物品可以重复选择,这种要怎么解决:
Fk(y):装前 k 种物品, 总重不超过 y, 背包的最大价值;
这里的子问题:很好理解,想一想,每一次你要去拿物品,你会想,
关于背包问题:
众所皆知,这里讲给出关于背包问题的一些简介:
一个旅行者准备随身携带一个背包. 可以放入背包的物品有n 种, 每种物品的重量和价值分别为 wj , vj . 如果背包的最大重量限制是 b, 怎样选择放入背包的物品以使得背包的价值最大?
先思考一个问题:就是每种物品可以重复选择,这种要怎么解决:
Fk(y):装前 k 种物品, 总重不超过 y, 背包的最大价值;
这里的子问题:很好理解,想一想,每一次你要去拿物品,你会想,