$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

模型：

$N$件物品和容量为$M$的背包，第$i$件物品的体积是$c_i$，价值是$v_i$。
求装入背包物品的最大价值

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

$f_{i,v}$表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：$f_{i,v}=max{f_{i-1,v},f_{i-1,v-c_i}+w_i}$。
所以直接上代码……

#include <bits/stdc++.h>
using namespace std;
int c[1010], w[1010], dp[1010][1010], n, m;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n; i++) scanf("%d%d", &c[i], &w[i]);
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= m; j++)
            if (j < c[i]) dp[i][j] = dp[i - 1][j];
            else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
    printf ("%d\n", dp[n][m]);
    return 0;
}

优化1：滚动数组

我们发现每一个$dp_{i,}$只和上一次的$dp_{i-1,}$有关，所以可以用滚动数组进行优化：

#include <bits/stdc++.h>
using namespace std;
int c[1010], w[1010], dp[2][1010], n, m;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n; i++) scanf("%d%d", &c[i], &w[i]);
    for (int i = 1;i <= n; i++)
        for (int j = 1;j <= m; j++)
            if (j < c[i]) dp[i & 1][j] = dp[(i - 1) & 1][j];
            else dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - c[i]] + w[i]);
    printf ("%d\n", dp[n & 1][m]);
    return 0;
}

这样，空间复杂度从$O(nm)$降低为$O(m)$，节省了很多空间。

优化2：一维数组

外层循环到第$i$个物品的时候，$f_j$表示背包中放入体积为$j$的物品的最大价值

#include <bits/stdc++.h>
using namespace std;
int c[1010], w[1010], dp[1010], n, m;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1;i <= n; i++) scanf("%d%d", &c[i], &w[i]);
    for (int i = 1;i <= n; i++)
        for (int j = m; j >= c[i]; j--)
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
    printf ("%d\n", dp[m]);
    return 0;
}