完全背包
一、问题形式
题目描述
有一个最多能装m公斤的背包，现在有n种物品，每种的重量分别是W1，W2，…，Wn，每种的价值分别为C1，C2，…，Cn。若每种物品的个数足够多，求能获得的最大总价值。
输入格式
第一行为两个整数，即m，n。
以后每行为两个整数，表示每件物品的重量和价值。
输出格式
获得的最大总价值。
样例
输入
5 5
1 1
2 2
3 3
4 4
5 5
输出
5
数据范围与提示
$ 1 \leq n \leq 100 $
$ 1 \leq m \leq 1000 $
$ 1 \leq c_i, w_i \leq 100 $
二、分析
法一
划分：
前i个背包容量j的最大价值；
阶段：
dp[i][j]:前i个背包容量j的最大价值；
转移：
i枚举数量，1~n;
j枚举容量：1~m;
k枚举选取数量的个数：0 ~ j/w[i];
每次取选与不选商品的最大值；
状态转移方程：
$ dp[i][j] = \max{dp[i - 1][j - k * w[i]] + c[i]} $
法二
思路：
因为k件数是有限的，即可将k消掉；
划分：
前i个背包容量j的最大价值；
阶段：
dp[i][j]:前i个背包容量j的最大价值；
转移：
i枚举数量，1~n;
j枚举容量：1~m;
每次取取与不取商品的价值最大值；
d
p
[
i
]
[
j
]
=
{
d
p
[
i
−
1
]
[
j
]
(
j
<
w
[
i
]
)
max
{
d
p
[
i
]
[
j
−
w
[
i
]
+
c
[
i
]
,
d
p
[
i
−
1
]
[
j
]
}
(
j
>
=
w
[
i
]
)
dp[i][j] = \begin{cases} dp[i - 1][j] & (j < w[i]) \\ \max\{dp[i][j - w[i] + c[i], dp[i - 1][j]\} & (j >= w[i]) \end{cases}
dp[i][j]={dp[i−1][j]max{dp[i][j−w[i]+c[i],dp[i−1][j]}(j<w[i])(j>=w[i])
法三
思路：
背包个数那一维，只用到了i - 1，所以用滚动数组优化；
划分：
容量j的最大价值；
阶段：
dp[j]:容量j的最大价值；
转移：
i枚举数量，1~n;
j用j-w[i]，从小到大枚举；
j枚举容量：w[i] ~ m;
每次比较取与不取时的价值最大值；
状态转移方程：
$ dp[j] = \max{dp[j], dp[j - w[i]] + c[i]} $
三、代码
法一
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, w[105], c[105], dp[105][1005];
int main() {
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &w[i], &c[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int k = 0; k <= j / w[i]; k++) {
dp[i][j] = max (dp[i][j], dp[i - 1][j - k * w[i]] + k * c[i]);
}
}
}
printf("%d", dp[n][m]);
return 0;
}
法二
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, w[105], c[105], dp[105][1005];
int main() {
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &w[i], &c[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j < w[i]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + c[i]);
}
}
}
printf("%d", dp[n][m]);
return 0;
}
法三
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, w[105], c[105], dp[1005];
int main() {
scanf("%d %d", &m, &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &w[i], &c[i]);
}
for (int i = 1; i <= n; i++) {
for (int j = w[i]; j <= m; j++) {
dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
}
}
printf("%d", dp[m]);
return 0;
}