完全背包问题

朴素做法：

核心状态转移方程如下：

d[i][j] = max(d[i][j], d[i-1][j - k*v[i]] + k * w[i]);

在推导的时候不难发现，如果j < v[i]的时候，应该取d[i][j] = d[i-1][j]，但是这个地方为什么是max(d[i][j],…)而不是max(d[i-1][j],…)呢？

首先肯定的是这样做一定是对的，那么我们丢失的d[i-1][j]到哪里去了呢？，仔细看完整的循环体你会发现：

for(int i = 1; i <= n; i ++ )
{
    for(int j = 1; j <= m; j ++ )
    {
        for(int k = 0; k * v[i] <= j; k ++ )
        {
            d[i][j] = max(d[i][j], d[i-1][j - k*v[i]] + k * w[i]);
        }
    }
}

当k等于0的时候，意味着我们取了0件i号物品，那么这个时候则有下述的推理逻辑：

$d[i][j] = max(d[i][j],d[i-1][j-0] + 0 * w[i])$

因为数组作为全局变量了，所以当第一次求d[i][j]的时候，d[i][j]默认就是0，所以max(0,d[i-1][j])就顺理成章的将d[i-1][j]更新给了d[i][j]，概言之就是d[i][j] = d[i-1][j]发生在了k = 0的时候

其次就是随着物品i数量的增加，我们应该不断更新的是取第i件物品时的最大利益，而不是一直与$d[i-1][j]$比较取最大值，所以这也就是为什么d[i][j] != max(d[i-1][j],d[i-1][j-kv[i]] + kw[i])

三重循环暴力DP代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n ; i ++ )
        scanf("%d%d", &v[i], &w[i]);
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 1; j <= m; j ++ )
        {
            for(int k = 0; k * v[i] <= j; k ++ )
            {
                d[i][j] = max(d[i][j], d[i-1][j - k*v[i]] + k * w[i]);
            }
        }
    }

    printf("%d", d[n][m]);

    return 0;
}

二维优化DP

受限于K的状态转移方程为：

for(int k = 0; k * v[i] <= j; k ++ )
{
    d[i][j] = max(d[i][j], d[i-1][j - k*v[i]] + k * w[i]);
}

根据上述式子可以推出:

$d[i][j] = max(d[i-1][j], d[i-1][j-v] + w, d[i-1][j-2v] + 2w, …)$ （①式）

同理可以推出：

$d[i][j-v] = max(d[i-1][j], d[i-1][j-v] , d[i-1][j-2v] + w, …)$ （②式）

可以得到如下递推关系：

$d[i][j] = max(d[i-1][j], d[i][j-v] + w)$ （③式）

通过③式不难看出，这里就成功的消掉了取物品数目k这一变量，进而砍掉了一个维度

二维DP代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n ; i ++ )
        scanf("%d%d", &v[i], &w[i]);
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 0; j <= m; j ++ )
        {
            //类似于01背包，只不过对比的式d[i][j-v[i]] + w[i]
            d[i][j] = d[i-1][j];
            if(j >= v[i]) d[i][j] = max(d[i][j], d[i][j - v[i]] + w[i]);
        }
    }

    printf("%d", d[n][m]);

    return 0;
}

终极优化，一维DP：

同01背包，完全背包利用的也是相邻两行之间的特征关系来递推出整个问题的代价，因此必然可以再砍掉一个维度
根据上述求出的递推关系式：

$d[i][j] = max(d[i][j], d[i][j - v[i]] + w[i]);$

d[i][j]的结果是用从前往后更新出来的，即取0个的代价–》取1个的代价-》取两个的代价，所以必须要从0开始更新代价，然后再用更新后的去继续更新，才能得到所有的最优解

一维DP代码：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

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

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n ; i ++ )
        scanf("%d%d", &v[i], &w[i]);
    for(int i = 1; i <= n; i ++ )
    {
        for(int j = 0; j <= m; j ++ )
        {
            if(j >= v[i]) d[j] = max(d[j], d[j - v[i]] + w[i]);
        }
    }

    printf("%d", d[m]);

    return 0;
}