很快小明的生日到了,小明的父母为了给小明过一个开心的生日,叫小明到城里唯一的一间儿童商店购买小明喜欢的商品,商店里共有n种商品,商品i的总重量为w[i],商品i总价值为v[i],小明带了一个背包去商店,背包最多能装M的重量,其中(1
很快小明的生日到了,小明的父母为了给小明过一个开心的生日,叫小明到城里唯一的一间儿童商店购买小明喜欢的商品,商店里共有n种商品,商品i的总重量为w[i],商品i总价值为v[i],小明带了一个背包去商店,背包最多能装M的重量。其中(1 <= i <= N, 0 < w[i] < M)。现在请你编一个程序帮小明算一算:怎样装才能使背包中装入的商品价值最高(对于每种商品i可以只装该商品的一部分x[i],当然也只能获得部分的价值:(x[i]/w[i])*v[i])。
(图片来源网络,侵删)
标签: ID 1325排序最大价值题解