二维数组

#include <bits/stdc++.h>
using namespace std;
int n, m;        // 物品数量、背包大小
int v[35];       // v[i]：第i件物品的大小
int w[35];       // w[i]：第i件物品的价值
int dp[35][205]; // dp[i][j]：前i件物品在j的体积下的最大价值
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // 求解dp数组
    for (int i = 1; i <= n; i++) // 物品
    {
        for (int j = 1; j <= m; j++) // 体积
        {
            // 求解 dp[i][j]，考虑是否选用了第i件物品
            // 如果没选用：答案为前 i-1 件物品在 j 的体积下的最大价值
            // 如果选用：第i件物品占用 v[i] 的背包大小
            //          前 i-1 件物品就只能使用 j-v[i] 的体积了
            if (j < v[i]) // 不能选用第i件物品
                dp[i][j] = dp[i - 1][j];
            else
                dp[i][j] = max(dp[i - 1][j], w[i] + dp[i - 1][j - v[i]]);
        }
    }
    // 输出
    cout << dp[n][m] << "\n";
    return 0;
}

滚动数组

#include <bits/stdc++.h>
using namespace std;
int n, m;   // 物品数量、背包大小
int v[35];  // v[i]：第i件物品的大小
int w[35];  // w[i]：第i件物品的价值
int a[205]; // dp[i-1][]
int b[205]; // dp[i][]
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // dp
    for (int i = 1; i <= n; i++)
    {
        // 由 a[] 推 b[]
        for (int j = 1; j <= m; j++)
        {
            if (j < v[i])
                b[j] = a[j];
            else
                b[j] = max(a[j], w[i] + a[j - v[i]]);
        }
        // 把 b[] 覆盖到 a[] 中
        for (int j = 1; j <= m; j++)
            a[j] = b[j];
    }
    // 输出
    cout << a[m] << "\n";
    return 0;
}

最终代码：一维数组在原数组上操作，逆序枚举体积，实现01背包

#include <bits/stdc++.h>
using namespace std;
int n, m;    // 物品数量、背包大小
int v[35];   // v[i]：第i件物品的大小
int w[35];   // w[i]：第i件物品的价值
int dp[205]; // dp[j]：j 的体积下的最大价值
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // dp
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
        {
            // dp[j+1]~dp[m] : 前 i 件物品的情况
            // dp[0] ~ dp[j] : 前 i-1 件物品的情况
            dp[j] = max(dp[j], w[i] + dp[j - v[i]]);
        }
    // 输出
    cout << dp[m] << "\n";
    return 0;
}

滚动数组求解的另一种写法

#include <bits/stdc++.h>
using namespace std;
int n, m;  // 物品数量、背包大小
int v[35]; // v[i]：第i件物品的大小
int w[35]; // w[i]：第i件物品的价值
// dp[1-now][] -> dp[i-1][]
// dp[now][] -> dp[i-1][]
int now, dp[2][205];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // dp
    now = 1;
    for (int i = 1; i <= n; i++)
    {
        // 由 a[] 推 b[]
        for (int j = 1; j <= m; j++)
        {
            if (j < v[i])
                dp[now][j] = dp[1 - now][j];
            else
                dp[now][j] = max(dp[1 - now][j], w[i] + dp[1 - now][j - v[i]]);
        }
        now = 1 - now;
    }
    // 输出
    cout << dp[1 - now][m] << "\n";
    return 0;
}

如果要求恰好装满可以这么做

#include <bits/stdc++.h>
using namespace std;
int n, m;    // 物品数量、背包大小
int v[35];   // v[i]：第i件物品的大小
int w[35];   // w[i]：第i件物品的价值
int dp[205]; // dp[j]：恰好装满 j 的体积时的最大价值
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // 输入
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // dp
    memset(dp, -1, sizeof(dp)); //-1表示无法装满
    dp[0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
        {
            // dp[j+1]~dp[m] : 前 i 件物品的情况
            // dp[0] ~ dp[j] : 前 i-1 件物品的情况
            if (dp[j - v[i]] != -1)
                dp[j] = max(dp[j], w[i] + dp[j - v[i]]);
        }
    // 输出
    int ans = -1;
    for (int i = 0; i <= m; i++)
        ans = max(ans, dp[i]);
    cout << ans << "\n";
    return 0;
}