完全背包.

题目描述
有N种物品和一个容量为 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是Ci，价值是Wi。求解在不超过背包容量的情况下，能够获得的最大价值。

背包双肩背包，输入
第一行为两个整数N、V(1≤N,V≤10000)，分别代表题目描述中的物品种类数量N和背包容量V。

后跟N行，第 i 行两个整数Ci、Vi，分别代表每种物品的体积和价值。

输出
输出一个整数，代表可获得的最大价值。

样例输入
5 20
2 3
3 4
10 9
5 2
11 11
样例输出
30
数据规模与约定
时间限制：1s

多背包问题，内存限制：64M

对于100%的数据，1≤N,V≤10000。

#include <iostream>
using namespace std;int weight, n, w[10005], v[10005], ans[10005][10005];int main() {cin >> n>> weight;for (int i = 1; i <= n; i++) {cin >> w[i] >> v[i];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= weight;j++) {if (j >= w[i]) {ans[i][j] = max(ans[i-1][j], v[i] + ans[i][j - w[i]]);}else {ans[i][j] = ans[i - 1][j];}}}cout << ans[n][weight] << endl;return 0;
}

数组压缩

#include <iostream>
using namespace std;int weight, n, w[10005], v[10005], ans[10005];int main() {cin >> n>> weight;for (int i = 1; i <= n; i++) {cin >> w[i] >> v[i];}for (int i = 1; i <= n; i++) {for (int j = 1; j <= weight;j++) {if (j >= w[i]) {ans[j] = max(ans[j], v[i] + ans[j - w[i]]);}}}cout << ans[weight] << endl;return 0;
}