题目描述

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤1000
0<vi,wi≤1000

样例

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10

算法1

(二维朴素做法) $O(n^2)$

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1010][1010];
int v[1010],w[1010];
int n,m;
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++)
        {
            f[i][j]=f[i-1][j];
            if(j>=v[i])
            {
                f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);
            }
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}

算法2

(一维优化空间做法) $O(n^2)$

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1010];
int v[1010],w[1010];
int n,m;
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=v[i];j<=m;j++)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    printf("%d\n",f[m]);
    return 0;
}

f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2v[i]]+2w[i],.....,f[i-1][j-kv[i]]+kw[i])
对照上面的式子，仿写
f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-2v[i]]+w[i],......,f[i-1][j-kv[i]]+(k-1)w[i])
通过观察发现max(f[i-1][j-v[i]]+w[i],f[i-1][j-2v[i]]+2w[i],.....,f[i-1][j-kv[i]+kw[i])这一长串
就是f[i][j-v[i]的式子再加上w[i]，就是那一长串
所以，f[i][j]=max(f[i-1][j]，f[i][j-v[i]]+w[i])。

上面就是把三维降到二维的原理
而要把二维降到一维，就需要等价变换了。通过对状态转移方程的观察，f[i][j]只需要上一轮f[i-1][j]的值，
和f[i][j-v[i]]的值，而这两个值通过顺序循环都是在f[i][j]计算之前就出现了，而这两个值，
也是通过他们之前的值推导出来的，所以只需知道前面的状态，就可以算出后面的值，不需要其他的没用的值
通过对数组的更新，只保留之前的值，以便于当前值的计算。

for(int i=1;i<=n;i++)
    {
        for(int j=v[i];j<=m;j++)
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
这个一维式子，逐步分析。
因为等号右边是已经算出来的值，那必然就代表着f[i-1][j]，等号左边是要被赋值的变量，所以是f[i][j]
而f[j-v[i]],因为体积是从v[i]到m，从小到大循环的，所以f[j-v[i]]肯定在第i层循环中已经有过了(有可能不是在第i层循环被算出来的，可能是在上一轮循环被算出来的，因为没被更新，所以一直保留着)，
所以代表着f[i][j-v[i]]。

这就是从三维到二维再到一维的简单推导