动态规划笔记（二）

内容概要：

动态规划的状态及状态转移
0-1背包问题
背包问题的若干变种
一道竞赛题Northwestern Europe 2002:Euro Efficiency

状态及状态转移方程

上篇文章我们知道，可以用动态规划解决的问题往往都具有重叠子问题和最优子结构，我们每次解决其中的一个子问题，最终将子问题的答案并到一块，原问题也就得到解决。为了更加清晰地描述这种求解(决策)过程，在动态规划中定义状态及状态转移。所谓状态就是在算法里我们要保存的每一步的求解结果，而状态转移就是后续要求解的子问题与当前已有的1个或多个状态之间的关系，或称状态转移方程。比如在求 $Fibonacci$ 数列的第 $n$ 项时，每一项都是一个状态，每求一个项只需要之前的两个状态，状态转移方程：
$a_n=a_{n-1}+a_{n-2},n \geq 3$

下面来通过一个简单的例子看一看状态及状态转移方程的作用：
LeetCode198 House Robber问题链接

LeetCode198

对于这个问题，定义状态：

$f(k) = 从[k,n) 房屋中能偷取到的最大钱数，nums[i]= 第 i 个房屋的钱数$

则有：
$f (n)=0,f(n-1)=nums[n-1]$ 这可以看做是系统初始状态，不难理解 $f(n)$ 表示没有可偷的房间，故为0； $f(n-1)$ 表示只能偷最后一个房间，故为 $nums[i]$ ，这样接着写下去：
$f (n-2)=max(nums[n-2],f(n-1)), f(n-3)=max(nums[n-3]+f(n-1),f(n-2))...$

不难写出对应的状态转移方程：
$f(k) = max(nums[k] + f(k+2),f(k+1))$

于是很轻松地给出动态规划代码：

class Solution198_1 {//动态规划
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)return 0;
        vector<int> memo(n+1, -1);
        memo[n] = 0; //抢劫[index,n)
        memo[n - 1] = nums[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            memo[i] = max(nums[i]+memo[i+2],memo[i+1]);
        }
        return memo[0];
    }
};

上述代码时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ (因为我们用memo将所有状态保存了下来。实际上如果看计算过程，会发现每个状态的求解只用到了前两个状态，故空间复杂度可以优化到 $O(1)$ )。

当然状态的定义也可以不同，这样一来得到的代码逻辑也会有区别，比如也可以定义
$f(k) = 从[0,k] 房屋中能偷取到的最大钱数，nums[i]= 第 i 个房屋的钱数$

此时 $f(1)=nums[1],f(2)=max(nums[1],nums[2])$ ，接着往下写不难得到状态转移方程：
$f(k) = max(nums[k] + f(k-2),f(k-1))$

对应的动态规划代码：

class Solution198_2 {//动态规划
public:
    int rob(vector<int>& nums) {
        int memo_pre = 0, memo_cur = 0;
        for (int i = 0; i < nums.size(); i++) {
            int temp = memo_cur;
            memo_cur = max(nums[i] + memo_pre, memo_cur);
            memo_pre = temp;
        }
        return memo_cur;
    }
};

该代码的时间复杂是 $O(n)$ ，空间复杂度是 $O(1)$ (因为只保留了会参与计算的两种状态。)

不管用哪种状态定义，我们看到，当状态和状态转移清晰时，代码的书写也会非常的流畅，所以有必要掌握寻找状态和状态转移方程的能力。下面再来看一个动态规划中的经典问题。

0-1背包问题

0-1背包问题描述：给定编号从0到n-1的一组物品，每种物品都有自己的重量w和价值v，现在有一个承重有限的背包，承重量为C，问：我们如何选择装入背包的物品，才能使得物品的总价值最高。
定义状态 $f(k,C)$ ：
$f(k,C)表示选择[0,k]区间的一些物品放入容量为C的背包，获得的最大价值，\\ w[k]表示第k个物品的重量，v[k]表示第k个物品的价值$ 于是得到状态转移方程： $f(k,C)=max(f(k-1,C),v[k]+f(k-1,C-w[k])$ 按照这个逻辑，首先给出问题的递归(记忆化搜索)代码：

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;
class Knapsack01_2 {
    // 记忆化搜索
// 时间复杂度: O(n * C) 其中n为物品个数; C为背包容积
// 空间复杂度: O(n * C)
public:
    vector<vector<int>>memo;
    //用[0,...,index] 的物品，填充容积为c的背包获得的最大价值
    int bestValue(const vector<int>& w, const vector<int> v, int index, int c) {
        if (index < 0 || c <= 0)return 0;//无法选物品或者没有容量
        if (memo[index][c] != -1)return memo[index][c];
        int res = bestValue(w, v, index - 1, c);//策略1，不选index号物品
        if (c >= w[index])//背包还能容纳编号为index的物品
            res = max(res, v[index] + bestValue(w, v, index - 1, c - w[index]));//策略2
        memo[index][c] = res;
        return res;
    }
    int solve(const vector<int>& w, const vector<int>& v, int C) {
        int n = w.size() - 1;
        memo = vector<vector<int>>(n, vector<int>(C + 1, -1));
        return bestValue(w, v, n - 1, C);
    }
};
int main() {//测试
    int n, C;
    cout << "请输入物品数量n和背包的承重量C：" << endl;
    cin >> n >> C;
    int v, w;
    vector<int> vs, ws;
    cout << "请输入各个物品的重量和价值：" << endl;
    for (int i = 0; i < n; i++) {
        cin >> w >> v;
        vs.push_back(v);
        ws.push_back(w);
    }
    cout << "最大价值为：" << Knapsack01_2().solve(ws, vs, C) << endl;
    return 0;
}

设背包承重量为5，各个物品重量和价值如下表，测试上述代码。

index	0	1	2	3
weight	1	2	3	4
value	9	10	12	8

测试结果如下：

0-1背包

可以检验，结果是正确的。
下面再给出动态规划的代码：

class Knapsack01_1 {
    // 动态规划O(n*C)O(n*C)
public: 
    int solve(const vector<int>& w, const vector<int>& v, int C) {
        assert(w.size() == v.size());
        int n = w.size();
        if (n == 0)return 0;
        vector<vector<int>>memo(n, vector<int>(C + 1, -1));
        for (int j = 0; j <= C; j++)
            memo[0][j] = (j >= w[0] ? v[0] : 0);//基础状态

        for (int i = 1; i < n; i++)
            for (int j = 0; j <= C; j++) {
                memo[i][j] = memo[i - 1][j];
                if (j >= w[i])
                    memo[i][j] = max(memo[i][j], v[i] + memo[i - 1][j - w[i]]);
            }
        return memo[n - 1][C];
    }
};

其中的状态量memo[i][j]表示[0:i]号物品放入承重量位j的背包的最大价值。
读者可自行测试其正确性。
0-1背包问题的空间复杂度优化
观察状态转移方程我们发现在求解一个新状态时，实际上只用到了两个状态，这样我们可以将空间复杂度优化到 $O(C)$ 。

class Knapsack01_3 {
public: 
    int solve3(const vector<int>& w, const vector<int>& v, int C) {
        assert(w.size() == v.size());
        int n = w.size();
        if (n == 0)return 0;
        vector<int>memo(C + 1, -1);
        for (int j = 0; j <= C; j++)
            memo[j] = (j >= w[0] ? v[0] : 0);//基础状态

        for (int i = 1; i < n; i++)
            for (int j = C; j >= w[i]; j--)
                memo[j] = max(memo[j], v[i] + memo[j - w[i]]);
        return memo[C];
    }
};

0-1背包问题的变种

完全背包问题和多重背包问题
完全背包问题是每种物品数量无限的背包问题，实际上由于背包容量有限，每种物品还是有上限的，这类问题可以转化为0-1背包问题。
多重背包问题是每种物品数量有限，同样可以转化为0-1背包问题。
多维费用背包问题
这类背包问题对背包的限制会增多，如从体积和容量两个维度约束背包。
物品互相排斥或依赖的背包问题
排斥：放入某些物品后就不能放入另一些物品了；
依赖：放入某些物品后必须放入另一些问题。
几个可转化为0-1背包问题的例子
LeetCode416 链接

LeetCode416

这个问题就是典型的0-1背包问题变种，相当于在 $n$ 个物品中选取一部分物品，填满容量为 $C$ 的背包(C在本题中为数组和的一半)，而且这个问题更加简单，因为不牵扯物品的价值，不过这里返回的是布尔值：
设 $f(n,C)$ 表示使用[0:n-1]的n个物品物品填满容量为 $C$ 的背包，于是对于 $\forall{k}$ ，有状态转移方程：
$f(k,C)=f(k-1,C)||f(k-1,C-w[i])$

它表示当考虑[0,k]区间的物品能否填满容量为C的背包时，首先看[0:k-1]是否能填满，否则看当前物品加入后是否能填满，也就是[0:k-1]是否能填满总容量C减去第k个物品的重量。
由状态转移方程，不难给出动态规划代码：

class Solution {//O(n*sum)
    //动态规划
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1)return false;
        int n = nums.size();
        int C = sum / 2;
        vector<bool>memo(C + 1, false);
        //看容量为i的情况下第一个物品是否能填满它
        for (int i = 0; i <= C; i++)
            memo[i] = (nums[0] == i);

        for (int k = 1; k < n; k++)
            for (int i = C; i >= nums[k]; i--)
                memo[i] = memo[i] || memo[i - nums[k]];
        return memo[C];
    }
};

LeetCode322 链接

LeetCode322

这个问题也是背包问题的一个简单变种，定义 $f(i)$ 为组成金额 $i$ 所需最少的硬币数量，则对应的状态转移方程应为：

$f(i)=(\min_{j=0 \ldots n-1}{f(i -w_j)} )+ 1$

其中 $w_j$ 代表的是第 $j$ 枚硬币的面值，上述状态转移方程的含义是，我们枚举的最后一枚硬币面额是 $w_j$ ，则需要从 $i-w_j$ 这个金额的状态 $f(i-w_j)$ 转移过来，再算上枚举的这枚硬币数量1的贡献，所以 $f(i)$ 为前面能转移过来的状态的最小值加上枚举的硬币数量1。动态规划代码：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //最坏全是1元硬币，不可能超过amount+1个;
        vector<int> memo(amount + 1, amount + 1);
        memo[0] = 0;//金额为0不能由硬币组成
        for (int i = 1; i <= amount; ++i) 
            for (int j = 0; j < coins.size(); ++j) 
                if (coins[j] <= i) 
                    memo[i] = min(memo[i], memo[i - coins[j]] + 1);
        return memo[amount] > amount ? -1 : memo[amount];
    }
};

一道竞赛题

Northwestern Europe 2002:Euro Efficiency
总时间限制: 1000ms 内存限制: 65536kB
描述
On January 1st 2002, The Netherlands, and several other European countries abandoned their national currency in favour of the Euro. This changed the ease of paying, and not just internationally.
A student buying a 68 guilder book before January 1st could pay for the book with one 50 guilder banknote and two 10 guilder banknotes, receiving two guilders in change. In short:50+10+10-1-1=68. Other ways of paying were: 50+25-5-1-1, or 100-25-5-1-1.Either way, there are always 5 units (banknotes or coins) involved in the payment process, and it
could not be done with less than 5 units.
Buying a 68 Euro book is easier these days: 50+20-2 = 68, so only 3 units are involved.This is no coincidence; in many other cases paying with euros is more efficient than paying with guilders. On average the Euro is more efficient. This has nothing to do, of course, with the value of the Euro, but with the units chosen. The units for guilders used to be: 1, 2.5, 5, 10, 25, 50,whereas the units for the Euro are: 1, 2, 5, 10, 20, 50.
For this problem we restrict ourselves to amounts up to 100 cents. The Euro has coins with values 1, 2, 5, 10, 20, 50 eurocents. In paying an arbitrary amount in the range [1, 100] eurocents, on average 2.96 coins are involved, either as payment or as change. The Euro series is not optimal in this sense. With coins 1, 24, 34, 39, 46, 50 an amount of 68 cents can be paid using two coins.The average number of coins involved in paying an amount in the range [1, 100] is 2.52.
Calculations with the latter series are more complex, however. That is, mental calculations.These calculations could easily be programmed in any mobile phone, which nearly everybody carries around nowadays. Preparing for the future, a committee of the European Central Bank is studying the efficiency of series of coins, to find the most efficient series for amounts up to 100 eurocents. They need your help.
Write a program that, given a series of coins, calculates the average and maximum number of coins needed to pay any amount up to and including 100 cents. You may assume that both parties involved have sufficient numbers of any coin at their disposal.
输入
The first line of the input contains the number of test cases. Each test case is described by 6 different positive integers on a single line: the values of the coins, in ascending order. The first number is always 1. The last number is less than 100.
输出
For each test case the output is a single line containing first the average and then the maximum number of coins involved in paying an amount in the range [1, 100]. These values are separated by a space. As in the example, the average should always contain two digits behind the decimal point. The maximum is always an integer.
样例输入

3
1 2 5 10 20 50
1 24 34 39 46 50
1 2 3 7 19 72

样例输出

2.96 5
2.52 3
2.80 4

题目解答过程

分析
题目的大意是，给定一组6种不同面值的硬币，每种硬币个数不限，现在你拿着这些硬币去购买价值为total_value的东西，问参与交易的最少硬币个数n是多少(可以多付钱，然后店家找钱)，编程计算当total_value从1到100需要的最少硬币个数求其均值，以及从1到100中最多需要的硬币个数。
例子
看一个简单的例子，为了例子的直观，现在假设只有三种面值的硬币1,2,10，求total_value从1到10需要的最少硬币个数均值，以及最多需要的硬币个数。
total_value=1时，1张面值为1的硬币就够了，min_count=1。
total_value=2时，1张面值为2的硬币就够了，min_count=1。
total_value=3时，需要1张面值为1的和1张面值为2的，min_count=2。
total_value=4时，需要2张面值为2的，min_count=2。
total_value=5时，需要2张面值为2的和1张面值为1的，min_count=3。
total_value=6时，需要3张面值为2的，min_count=3。
total_value=7时，注意虽然可以3张面值2加1张面值1，这样一共用4张；但是如果1张面值10的给店家，店家找1张面值2的和1张面值1的，交易只用了三张，因此是min_count=3。
total_value=8时，给1张面值10的，找一张面值2的，min_count=2。
total_value=9时，给1张面值10的，找一张面值1的，min_count=2。
total_value=10时，min_count=1。

total_value	1	2	3	4	5	6	7	8	9	10
min_count	1	1	2	2	3	3	3	2	2	1

于是需要的硬币个数均值：
$Ave = \frac {1+1+2+2+3+3+3+2+2+1}{10}=2$

其中的最大值：
$max\_use=3$

问题的抽象
由上面的分析可以将问题抽象为一个类完全背包问题，用动态规划解决。设硬币面值数组为 $coins[6]$ 。定义状态 $memo[k]$ 表示购买价值为 $k$ 的物品需要参与交易的最少硬币数量。
不过由于存在可以多付钱然后再找钱的过程，背包的容量并不是每次购买的物品的价值 $k$ ，所以memo数组的空间一定要大于100。于是将动态规划分为两个阶段，第一个阶段只考虑付钱而不找钱来计算 $memo[k]$ ，初始 $memo[0]=0$ ，状态转移方程：
$memo[k]=min(memo[k],memo[k-coins[j]]+1),j \in [0,6)$

第二个阶段来考虑找钱，比如我们的简单例子中，在第一阶段会求得 $7=2+2+2+1$ ，用了4个硬币，现在考虑多付钱然后找钱的过程，可以付8找1，付9找2，付10找3，由于店家找钱也是用硬币组合为需要找给买家的价值，所以其实在第一个阶段求解过，于是状态转移方程：
$memo[k] = min(memo[k], memo[k + coin[j]] + 1),j \in [0,6)$

自此问题已经很清晰了，给出动态规划代码：

# include<cstdio>
# include<algorithm>
# include<cmath>
# include<iostream>
using namespace std;
int INF = 0x3f3f3f3f;
const int maxn = 1000; // 不能写100，因为有找钱会减，中间状态可能大于100

int memo[maxn];// memo[k]
int main() {
    int n;
    // freopen("input.txt", "r", stdin);
    cin >> n;//scanf_s("%d", &n);
    int coin[10];
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= 6; j++)
            cin >> coin[j]; //scanf("%d", &coin[j]);
        memo[0] = 0; // 初始化
        for (int j = 1; j < maxn; j++)
            memo[j] = INF;
        // 动态规划
        for (int j = 1; j <= 6; j++)
            for (int k = coin[j]; k <= maxn; k++)
                if (memo[k - coin[j]] != INF)
                    memo[k] = min(memo[k], memo[k - coin[j]] + 1);
        
        for (int j = 1; j <= 6; j++)
            for (int k = maxn - coin[j]; k >= 0; k--)
                if (memo[k + coin[j]] != INF)
                    memo[k] = min(memo[k], memo[k + coin[j]] + 1);
        int sum = 0, max_count = -1;
        for (int j = 1; j <= 100; j++) {
            sum += memo[j];
            max_count = max(max_count, memo[j]);
        }
        double ave = (double)sum / 100;
        printf("%.2lf %d\n", ave, max_count);
    }
    // fclose(stdin);
    return 0;
}