ACDaily 4

不简单DP

01背包问题

有 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

输出样例：

8

题解:

这道题若使用暴力做法，可以将题意转化为：给定n位二进制序列（即n个物品，若该位为1，则表示选择该物品，反之不选择），每一位对应一个价值和一个体积，枚举所有所有可能的组合，先判断能不能装进背包，若能装，则计算总价值，更新当前最大价值，反之，不更新最大价值，最后输出最大价值即可。通过分析，我们可以发现这种做法的复杂度为指数级别，超时不可避免，因此我们需要优化算法。

1.用二维数组做动态决策

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;
int v[N], w[N], f[N][N];  // f数组记录的是j体积下前i个物品的最大价值

int main()
{
    int n, m;
    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 = 1; j <= m; j++)
        {
            if(j < v[i]) f[i][j] = f[i-1][j];  // 难点在于为什么判断j < v[i]就可以，因为前i-1间物品是可选可不选的
            else{
                f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]); 
            }
        }
    
    cout << f[n][m] << endl;
    return 0;
}

本方法的关键在于**构造j体积背包下的i个物品的最大价值数组f[N][N]**。那么为什么要做这样的假设呢，因为我们最终要求的是背包容量为j的i个物品的最大价值，由递推的思想，j体积背包下前i个物品的最大价值可以由前i-1个物品的最大价值来推导，因此我们可以从最原始的状态出发，不断增加物品数量，在每个物品数量i下，背包的体积j从1开始增长到m，通过对这些情况进行依次判断与选择来确定j体积背包下前i个物品的最大价值。

2.优化：用一维数组做动态决策

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;
int v[N], w[N], f[N];  // 本方法中的假设与一般方法相同，使用降维的方法，将一些冗余的数值剔除了（可以单步模拟之后的遍历来观察）

int main()
{
    int n, m;
    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] << endl;
    return 0;
}

使用该种优化后，可以省略掉j与v[i]的判断语句，优化循环的终止条件。但要注意j为逆序遍历，这样做的原因是防止当前最大价值计算时需要用到的之前最大价值被污染，这一点也可以通过简单的模拟来实现。

3.输入优化

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int f[MAXN];  // 

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

    for(int i = 1; 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;
}

由于两个循环皆有边读入边处理的特性，因此我们可以将这两个循环进行一个合并，减小语句长度。

以上就是对该类问题初步理解而做出的阐述，后续再遇到此类问题时会对内容进行一个更清晰的重构。

对此问题更好的解释可以参考状态转移方程的解释。