题目描述

有 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

发现01背包和完全背包两者本质就是j从小到大和从大到小。

01背包C++ 代码

#include <iostream>
// 数组小标代表单位体积，数组值为当前体积最大价值 
using namespace std;

const int N = 1010;

int n, m;
int f[N];

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

    cout << f[m] << endl;

    return 0;
}

完全背包代码

#include <iostream>
// 数组小标代表单位体积，数组值为当前体积最大价值 
using namespace std;

const int N = 1010;

int n, m;
int f[N];

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

    cout << f[m] << endl;

    return 0;
    }

我简要描述f的变化

01背包

       i=0，j=5,v=1,w=2;  f0=0,f1=0,f2=0...f5=2;
       i=0,j=4;  f0=0,f1=0;.. f4=2,f5=2;
       i=0;j=3;f0=0;...f3=2,f4=2,f5=2;
       ...
       i=0,j=0; f0=0;f(1~5)=2;
       i=1;j=5;v=2,w=4;f0=0;f1=2,f2=2;f3=2;f4=2;f5=6;
       ...
       i=1;j=0; f0=0;f1=2;f2=4;f3=6;f4=6;f5=6;
       可以看出从后往前比较大值；

完全背包

      i=0，j=1，v=1，w=2;   f0=0,f1=2,f2=0...f5=0;
       i=0, j=2;   f0=0,f1=2，f2=4;.. f4=0,f5=0;
       i=0;j=3;   f0=0;f1=2;f2=4;f3=6;f4=0;f5=0;
       ...
       i=0,j=0; f0=0;f(1~5)=2,4,6,8,10;
       i=1;j=5,v=2,w=4;f0=0;f1=2,f2=4;f3=6;f4=8;f5=max(f[5]=10,f[3](f3=6)+w(w=4))=10;
       ...
       i=1;j=0; f0=0;f1=2;f2=4;f3=6;f4=8;f5=10;   
       可以看出从前往后比较计算，当前数据的前一数据已更新。

看了Y总的视频，吸收的不够透彻，我只是从代码的比较看出一些规律

    完全 j=v;j<m;j++ 计算当前物品的出现的i~k次的最大和
    01   j=m;j>+v;j--  前i物品的最大和

可能表达不够透彻，用最直接的方法打断点看f数组的值，你就会发现什么的。