问题描述

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

例：背包最大重量为4，物品如下：

问 背包能被的物品最大价值是多少？

解题方法

在 0-1背包 问题中，由于每个物体只能选取一次，所以内嵌循环采用从大到小的顺序，而在 完全背包 问题中，每个物品可以被选取不止一次，因此需要采用从小到大的顺序进行遍历。

for(int i=0; i<weight.size(); i++) {
    for(int j=weight[i]; j<=bagweight; j++) {
        dp[j] = max(dp[j], dp[j-weight[i]] + value[i]);
    }
}