背包问题的一个变种

灵感来自:http://poj.org/problem?id=1042

已知背包容量固定且为单位体积的N倍。

物品种类固定为M

每种物品都没有数量上限

每件物品的体积都是单位体积

每件物品的价值与背包中该类物品的数量有关,物品的价值与背包内该物品的数量成一次函数关系

第i 种物品的初始价值为fi,背包里每有一件该类物品,下一件该类物品的价值降低di

  例:A货物的初始价值f1=10,价值递减系数di=1,背包中如果有两件A货物,其价值总和即为10+9=19

给出N,M,fi,di,求一个能得出最佳选择能使背包中物品的价值最高的算法

其时间复杂度应当低于N*M

如何设计该算法,能否使该算法的时间复杂度为N+M?

原文地址:https://www.cnblogs.com/liujinming/p/7586884.html