本文最后更新于 42 天前，其中的信息可能已经有所发展或是发生改变。
例题
设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。
个人思路
翻译过来就是0-1背包问题但物品无限版本。参考一维数组滚动优化思路（倒过来遍历是为了不干扰上一回合的数据），那么完全背包问题就要对之前的数据进行干预，那么只需要把0-1背包问题中滚动优化之中的遍历顺序编程正序即可。
代码演示
#include <iostream>
#include <vector>
using namespace std;
int n;
int m;
struct Item {
int w;
int v;
};
int backsoft(vector<Item>& items){
vector<int> dp(m+1, 0);
for(int i = 0 ; i < n ; i++){
for(int k = items[i].w ; k <= m ; k++){
dp[k] = max(dp[k],dp[k-items[i].w]+items[i].v);
}
}
return dp[m];
}
int main() {
cin >> m >> n;
vector<Item> items(n);
for (int i = 0; i < n; i++) {
cin >> items[i].w >> items[i].v;
}
cout << "max=" << backsoft(items) << endl;
return 0;
}