01背包

（1） 二维数组做法

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1002;
int v[N];  //体积
int w[N];  //价值
int f[N][N];  //f[i][j]表示前i个物品，背包容量为j的最优解

int main()
{
    int n, m;  //n是物品数，m是总容量
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];  //不含i
            if (j >= v[i])  //剩余体积要能装下第i件物品，才含i
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  //看是否选择装第i个物品
                //很难求含i的情况，所以选择通过将第i个物品的体积减去，算出不含i的最大值，再将i的价值加回来
        }
    }

    cout << f[n][m] << endl;

    return 0;
}

（2）一维数组做法（优化版）

#include <iostream>
#include<algorithm>

using namespace std;

const int N = 1002;
int v[N];  //体积
int w[N];  //价值
int f[N];  //最优解

int main()
{
    int n, m;  //n是物品数，m是总容量
    cin >> n >> m;

    for (int i = 1; i <= n; i ++ )
        cin >> v[i] >> w[i];

    for (int i = 1; i <= n; i ++ )
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;

    return 0;
}