https://www.acwing.com/problem/content/3/
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤1000
0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1100;
int f[N][N], v[N], w[N];
int main() {
int n, m,i,j,k;
cin >> n >> m;
for (i = 1; i <= n; i++) cin >> v[i] >> w[i]; // 体积和价值
for (i = 1; i <= n; i++) // 前i类
for (j = 1; j <= m; j++) // 容积
for (k = 0; k * v[i] <= j; k++) // 第i类物品被容积允许的数量
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
cout << f[n][m];
return 0;
}
f(i,j) = max( f(i,j),f(i,j-ui)+wi)
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1100;
int f[N][N], v[N], w[N];
int main() {
int n, m,i,j,k;
cin >> n >> m;
for (i = 1; i <= n; i++) cin >> v[i] >> w[i]; // 体积和价值
for (i = 1; i <= n; i++) { // 前i类
for (j = 0; j <= m; j++) { // 容积
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
}
cout << f[n][m];
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1100;
int f[N], v[N], w[N];
int main() {
int n, m, i, j, k;
cin >> n >> m;
for (i = 1; i <= n; i++) cin >> v[i] >> w[i]; // 体积和价值
for (i = 1; i <= n; i++) // 物品类数
for (j = v[i]; j <= m; j++) { // 容积
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
cout << f[m];
return 0;
}
http://poj.org/problem?id=1384
Sample Input:（今加注释处理方便理解）
3 #测试案例数量
10 110 # 1 <= E <= F <= 10000 金额取值范围
2 # 1 <= N <= 500 种类
1 1 # 1 <= P <= 50000, 1 <= W <= 10000 金额，价格
30 50 # 1 <= P <= 50000, 1 <= W <= 10000 金额，价格
10 110
2
1 1
50 30
1 6
2
10 3
20 4
Sample Output:
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
输入输入包含T个测试用例。
它们的数量（T）在输入文件的第一行上给出。
每个测试用例均以包含两个整数E和F的行开头。它们表示空猪和装满硬币的猪的重量。
两种重量均以克为单位。
没有猪的重量超过10公斤，这意味着1 <= E <= F <= 10000。
在每个测试用例的第二行，都有一个整数N（1 <= N <= 500）给出该数字给定货币使用的各种硬币的集合。
紧随其后的是N行，每行指定一种硬币类型。这些行分别包含两个整数Pand W（1 <= P <= 50000，1 <= W u <= 10000）。 P是硬币的货币单位价值，W是重量（克）。
#include<iostream>
#include<math.h>
#define N 500
#define inf 10000000
#define MAX_F 10000
using namespace std;
int dp[MAX_F + 1];
int p[N + 1];
int w[N + 1];
int main() {
int time;
cin >> time;
while (time--) {
int e, f, n, m;
cin >> e >> f; // 它们表示空猪和装满硬币的猪的重量
m = f - e; // 容积限制
cin >> n; // 硬币种类
for (int i = 1; i <= n; i++) {
cin >> p[i] >> w[i]; // P是硬币的货币单位价值，W是重量（克）。
}
for (int i = 0; i <= m; i++) {
dp[i] = inf;
}
dp[0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
dp[j] = min(dp[j], dp[j - w[i]] + p[i]);
}
}
if (dp[m] == inf) {
cout << "This is impossible." << endl;
}
else {
cout << "The minimum amount of money in the piggy-bank is " << dp[m] << "." << endl;
}
}
system("pause");
return 0;
}
