淡定冰淇淋

文章
3
资源
0
加入时间
4年0月8天

【动态规划】完全背包问题-疯狂的采药

什么是完全背包问题?有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。这里不同之处是每件物品可无限取,这里就产生了很多可行的优化,比如同体积的有多种物品,则必然可以舍弃价值小的,也可以舍弃体积大于v的。比较一下01背包问题:在M件物品中取出若干件物品放到背包中,每件物品对应的体...