01背包的DP分析

状态表示：f[i][j] 从前i个物品中选，所选物品体积不超过j的所有选法的集合，

每一个选法代表一个价值，集合属性是集合中的价值最大值。f[i][j]代表这样的价值最大值。

而f[n][m]就是题目要求的答案了

状态计算：f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);（选不选第i个物品，选还涉及体积大小问题（下标问题））

状态初始化：f[0][0~m] = f[0~n][0] = 0;

一维优化的逻辑：第i层的数据更新只用到了i - 1层的数据。其他层的数据可以去除。

j逆序的逻辑：第i层数据更新需要第i - 1层的数据，

顺序的话，更新j时，j之前的更新过，错误地用到第i层的数据。

逆序的话，更新j时，j之前的没更新过，正确地用到第i - 1层的数据

二维朴素

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m;
int v[N], w[N];
int f[N][N];

int main()
{
    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 = 0; j <= m; j++)
        {
            f[i][j] = f[i-1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }    

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

    return 0;
}

二维输入优化

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m;

int f[N][N];

int main()
{
    cin >> n >> m;


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

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

    return 0;
}

二维空间优化->一维

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m;
int v[N], w[N];
int f[N];

int main()
{
    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];

    return 0;
}

一维输入优化(速度最快)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n,m;
int v, w;
int f[N];

int main()
{
    cin >> n >> m;


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

    }
    cout << f[m];

    return 0;
}