01背包问题思路分析

闫氏分析法

                             | 集合 ： 从1 ~ i 种物品中选取，且体积小于 j 的一类集合
                             |
  |------------状态表示 -----|
  |                          | 属性 :  集合中可行方案价值最大的值 max
  | 
  | 
  |
  DP    
  |
  |
  |
  |
  |------------状态计算 : 根据集合划分，将一个大集合划分为若干个子集， 
                          设我们要求解f(i,j), 然后来尝试将其分为更小的集合

对集合f(i,j) , 这个集合我们可以把它先分为两部分， 一部分是 (1) 不包含第 i 种物品的可行方案数，(2) 必包含第 i 种物品的可行方案

      |----------------(1)  不包含第 i 种物品且总体积不大于j的集合为 f(i - 1, j)， f(i - 1, j) 的值即为这个集合中价值的最大值
      |  
      |
    f(i,j)
      |
      |----------------(2)  必包含第 i 种物品的可行方案的集和， 其值等价于 f(i - 1,  j = V[i] ) + W[i] , 因为第i个物品必选，故此时
                            等价于在 i - 1 种物品中选，且体积不大于 j - V[i](减去第i个物品的体积)的集合的最大值 再加上第i个物品的价值

故由于将我们的集合分为这两部分，但我们存的是所有子集中的价值最大的，故f(i,j) = max(f(i - 1, j) , f(i - 1, j - V[i]) + W[i] );
但注意(2) 部分集合有可能是空集，只有当 j >= V[i] 才存在第二部分，才能进行max比较. 实现代码如下

#include<iostream>
using namespace std;

constexpr int N = 1010;

int V[N], W[N];
int n,v;
int f[N][N];

auto main() -> int
{
    cin >> n >> v;
    for(int i = 1; i <= n; ++i) cin >> V[i] >> W[i];

    for(int i = 1; i <= n; ++i)
    {
    for(int j = 1; j <= v; ++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][v] << endl;

    return 0;
}

做优化 ， 优化空间，将一维数组优化为二维数组

先直接去掉第一维， 然后观察式子是否与原来等价

#include<iostream>
using namespace std;

constexpr int N = 1010;

int V[N], W[N];
int n,v;
int f[N];                    // 直接去掉第一维

auto main() -> int
{
    cin >> n >> v;
    for(int i = 1; i <= n; ++i) cin >> V[i] >> W[i];

    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= v; ++j)
            {
                f[j] = f[j];          // 去掉第一维后变为恒等式， 故这个式子可以直接去掉
                if(j >= V[i]) f[j] = max(f[j], f[j - V[i]] + W[i]);     // 这里将第一维去掉，但要考虑个问题，由于原题目中的这里取的都是前面推导过的f(i - 1, j) 和 f(i - 1, j - V[i]);
            }                                                           // 故去掉第一维之后看看是否新的一层是否会把之前覆盖为新值，这里观察是会的，因为这里的f(i - 1, j - V[i]) 中的
    }                                                                   // j - V[i] 必定小于 j, 故这个值在之前就被新的值覆盖，故解决这个问题可以将这里的内层for从大到小循环。
   cout << f[v] << endl;

    return 0;
}

空间优化后的代码

#include<iostream>
using namespace std;

constexpr int N = 1010;

int V[N], W[N];
int n,v;
int f[N];

auto main() -> int
{
    cin >> n >> v;
    for(int i = 1; i <= n; ++i) cin >> V[i] >> W[i];

    for(int i = 1; i <= n; ++i)            
        for(int j = v; j >= 1; --j)           // 注意这里的j 是 从 v开始， 然后 --j
            if(j >= V[i]) f[j] = max(f[j], f[j - V[i]] + W[i]);

   cout << f[v] << endl;

    return 0;
}