动态规划问题中边界和边界值的确定

引言

在动态规划问题中，首先需要抽象出原问题的状态，然后写出状态转移方程，最后根据边界状态值和转移方程求解所有的状态。在本文中，我们将以01背包问题为例来探讨分析如何确定边界状态和边界状态值。

01背包问题的最优方案数（原题链接）

题目描述

有$n$件物品，每件物品的重量为$w_i$，价值为$c_i$。现在需要选出若干件物品放入一个容量为$V$的背包中（每件物品至多选一次），使得在选入背包的物品重量之和不超过容量$V$的前提下，让背包中物品的价值之和最大，求最大价值与对应的最优方案数。

输入描述

第一行两个整数$n$、$V$ $(1\le n\le 100,1\le V\le 10^3)$，分别表示物品数量、背包容量；

第二行为用空格隔开的$n$​个整数$w_i$（$1\le w_i\le 100$​），表示物品重量；

第三行为用空格隔开的$n$​个整数​$c_i$（$1\le c_i\le 100$​），表示物品价值。

输出描述

输出两个整数，分别表示最大价值与最优方案数，中间用空格隔开。由于结果可能很大，因此将结果对
取模后输出。

样例1

输入

3 5
1 2 5
4 2 6

输出

6 2

解释
假设物品编号为从1到3，那么选择第1、2件物品、或者只选择第3件物品时，物品重量不会超过背包容量，对应的价值是$4+2=6$​​，是最大价值。因此共有2种最优方案。

问题分析

这个问题需要求解两个值，分别是最大价值和最优方案数。

最大价值

对于最大价值，令dp[i][v]表示从前i件物品中选择若干件装入容量为v的背包，在不超过背包容量的前提下，所能装入的最大物品价值。其状态转移方程为：
$$\text{dp[i][v]}=\{\begin{array}{rl}& \text{dp[i-1][v]},\text{if v < w[i] or dp[i-1][v] > dp[i-1][v-w[i]] + c[i]}\\ & \text{dp[i-1][v-w[i]] + c[i]},\text{else}\end{array}$$
接下来确定上述状态转移方程的边界。对于dp数组的第一维，计算dp[1][v]时，需要用到dp[0][v]，同时发现无法通过状态转移方程计算dp[0][v]，因此dp[0][v] ($0\le v\le V$)就是一组边界。对于dp数组的第二维，计算dp[i][0]时，需要用到dp[i-1][0]，通过递推可知最终需要用到dp[0][0]。综上所述，这个状态转移方程的边界为：dp[0][v] ($0\le v\le V$)。

边界的含义是从前0件物品中选若干件装入容量为v的背包中所能获得的最大价值，根据这个意义应该有dp[0][v] = 0。换个角度考虑，整个状态转移方程是从此边界开始的，因此dp[0][v]应该等于dp数组所能取到的最小值，而这个最小值恰好是0。

最优方案数

对于最优方案数，令cnt[i][v]表示从前i件物品中选择若干件装入容量为v的背包中，可以使得背包中物品价值最大的装入方案数。其状态转移方程为：
$$\text{cnt[i][v]}=\{\begin{array}{rl}& \text{cnt[i-1][v]},\text{if v < w[i] or dp[i-1][v] > dp[i-1][v-w[i]] + c[i]}\\ & \text{cnt[i-1][v-w[i]]},\text{if v≥w[i] and dp[i-1][v] > dp[i-1][v-w[i]] + c[i]}\\ & \text{cnt[i-1][v]+cnt[i-1][v-w[i]]},\text{if v≥w[i] and dp[i-1][v] == dp[i-1][v-w[i]] + c[i]}\end{array}$$
接下来确定上述状态转移方程的边界。对于cnt数组的第一维，计算cnt[1][v]时，需要用到cnt[0][v]，同时发现无法通过状态转移方程计算cnt[0][v]，因此cnt[0][v]($0\le v\le V$)就是一组边界。对于cnt数组的第二维，计算cnt[i][0]时，需要用到cnt[i-1][0]，通过递推可知最终需要用到cnt[0][0]。综上所述，这个状态转移方程的边界为：cnt[0][v]($0\le v\le V$)。

与dp数组的边界值不同，cnt数组的边界值不太容易通过边界的含义来确定，因为cnt[0][v]的含义是从前0件物品中选若干件装入容量为v的背包中，可以使得背包中物品价值最大的装入方案数。我们从cnt数组的取值范围来考虑，根据题意，最优解是一定存在的，只不过是存在几个最优解的问题。根据状态转移方程，在一定的条件下，有cnt[1][v]=cnt[0][v]，显然cnt[1][v]的值至少是1，因此cnt[0][v]的值应该初始化为1。

源代码

在上面的讨论中，用于记录状态的dp和cnt都是二维数组，整个算法的空间复杂度为O(nV)。我们可以通过滚动数组的方式，将空间复杂度减小到O(V)，下面分别给出空间复杂度为O(nV)和O(V)的实现。

O(nV)空间复杂度

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int maxV = 1e3 + 5;
int dp[maxn][maxV];
int cnt[maxn][maxV];
int n, V;
int w[maxn], c[maxn];

int main(){
    scanf("%d %d", &n, &V);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    //初始化dp和cnt数组
    for(int v = 0; v <= V; v++){
        dp[0][v] = 0;
        cnt[0][v] = 1;
    }
    for(int i = 1; i <= n; i++){
        for(int v = 0; v <= V; v++){
            dp[i][v] = dp[i - 1][v];
            cnt[i][v] = cnt[i - 1][v];
            if(v >= w[i] && dp[i][v] < dp[i - 1][v - w[i]] + c[i]){
                dp[i][v] = dp[i - 1][v - w[i]] + c[i];
                cnt[i][v] = cnt[i - 1][v - w[i]];
            }else if(v >= w[i] && dp[i][v] == dp[i - 1][v - w[i]] + c[i]){
                cnt[i][v] = (cnt[i][v] + cnt[i - 1][v - w[i]]) % 10007;
            }
        }
    }
    printf("%d %d", dp[n][V], cnt[n][V]);

}

O(V)空间复杂度

#include<bits/stdc++.h>
using namespace std;
const int maxn = 105;
const int maxV = 1e3 + 5;
int dp[maxV];
int cnt[maxV];
int n, V;
int w[maxn], c[maxn];

int main(){
    scanf("%d %d", &n, &V);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    for(int i = 1; i <= n; i++)
        scanf("%d", &c[i]);
    //初始化dp和cnt数组
    for(int v = 0; v <= V; v++){
        dp[v] = 0;
        cnt[v] = 1;
    }
    for(int i = 1; i <= n; i++){
        for(int v = V; v >= 0; v--){
            if(v >= w[i] && dp[v] < dp[v - w[i]] + c[i]){
                dp[v] = dp[v - w[i]] + c[i];
                cnt[v] = cnt[v - w[i]];
            }else if(v >= w[i] && dp[v] == dp[v - w[i]] + c[i]){
                cnt[v] = (cnt[v] + cnt[v - w[i]]) % 10007;
            }
        }
    }
    printf("%d %d", dp[V], cnt[V]);
}

参考

胡凡、曾磊《算法笔记》