【动态规划】MATLAB和Python实现-Part04_基于matlab的动态规划程序实现

往期系列：
【动态规划】MATLAB和Python实现-Part01

【动态规划】MATLAB和Python实现-Part02

【动态规划】MATLAB和Python实现-Part03

---

零、回顾

前面三篇文章，我们从递归开始，了解了动态规划，并从实际例子中体会动态规划的过程。

---

本篇文章我们继续以实际例子体会动态规划。
我们再回想一下动态规划的基本思路：

• 定义原问题和子问题
• 定义状态
• 寻找状态转移方程
• 编程求解

一、0-1背包问题

1.1 题目描述

有 10 件货物要从甲地运送到乙地，每件货物的重量和利润如下表所示：

由于只有一辆最大载重为 30 的火车能用来运送货物，所以只能选择部分货物进行配送，要求确定运送哪些货物，使得运送这些货物的总利润最大。

1.2 题目分析

定义原问题和子问题：
原问题：
假设有 $m$ 件物品，其中第 $k$ 件物品的利润为 $v_k$，重量为 $w_k$，背包能容纳的总重量为 $W$，在满足重量约束的条件下，将这 $m$ 件物品选择性地放入容量为 $W$ 的背包，求解出所能获得的最大利润。
（假设这里的重量和利润都为正整数。）
子问题：
在满足重量约束的条件下，将前 $i(i\le m)$ 件物品选择性地放入容量为 $j(j\le W)$ 的背包中所能获得的最大利润。

定义状态：
记前 $i$ 件物品选择性地放入容量为 $j$ 的背包中所能获得的最大利润为 $f(i,j)$，那么 $f(m,W)$ 就是我们要求解的原问题的答案。
这里的 $i$ 和 $j$ 构成的组合就是对应子问题的状态。

寻找状态转移方程：
对于 二维 情况，我们可以先考虑问题的 边界条件：

• 边界条件1： 当 $i=1$ 时，$f(1,j)$ 表示把第 1 件物品放入容量为 $j$ 的背包中所能获得的最大利润，显然当 $j\ge w_1$，即背包容量大于等于第 1 件物品的重量，就有 $f(1,j)=v_1$，否则有 $f(1,j)=0$；
• 边界条件2： 当 $j=1$ 时，$f(i,1)$ 表示容量为 $1$ 时，把第 $i$ 件物品放入背包中所能获得的最大利润，显然当 $w_i=1$ 时，有 $f(i,1)=v_i$，否则有 $f(i,1)=0$

接下来考虑问题的一般情况，即当 $i,j>1$ 时：
假设现在背包容量为 $j$，前面 $i-1$ 件物品已经规划好了方案，现在要考虑是否装第 $i$ 件物品，该问题可以分为两种情况考虑（此时我们先不考虑前 $i-1$ 件物品，假设背包为空）：

• 第 $i$ 件物品的重量 $w_i$ 比背包的容量 $j$ 还要大： 这时候我们只能放弃物品 $i$，那么就有 $f(i,j)=f(i-1,j)$；
• 第 $i$ 件物品的重量 $w_i$ 比背包的容量 $j$ 的容量小： 这时候我们可以选择将其放入背包或者不放入。如果放入，则有 $f(i,j)=v_i+f(i-1,j-w_i)$，即放入第 $i$ 件物品后，将剩余空间留给前 $i-1$ 件物品；如果不放入，则有 $f(i,j)=f(i-1,j)$；所以有： f ( i , j ) = m a x { v i + f ( i − 1 , j − w i ) , f ( i − 1 , j ) } f(i,j)=max\{v_{i}+f(i-1,j-w_{i}),f(i-1,j)\} f(i,j)=max{vi​+f(i−1,j−wi​),f(i−1,j)}.
  （若 $w_i=j$ ，则令 $f(i-1,j-w_i)=0$）

综上所述，最终的状态转移方程为：
f ( i , j ) = { 0 i = 1 , j < w 1 v 1 i = 1 , j ≥ w 1 0 w i > 1 , j = 1 v i w i = 1 , j = 1 f ( i − 1 , j ) w i > j , i > 1 , j > 1 m a x { v i + f ( i − 1 , j − w i ) , f ( i − 1 , j ) } w i ≤ j , i > 1 , j > 1 f(i,j)=

$$\begin{cases} 0 & i=1, j<w_{1}\\ v_{1} & i=1,j\geq w_{1} \\ 0 & w_{i}>1,j=1\\ v_{i} & w_{i}= 1,j=1\\ f(i-1,j) & w_{i}>j,i>1,j>1 \\ max\{v_{i}+f(i-1,j-w_{i}),f(i-1,j)\} & w_{i}\leq j,i>1,j>1 \end{cases}$$ f(i,j)=⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​0v1​0vi​f(i−1,j)max{vi​+f(i−1,j−wi​),f(i−1,j)}​i=1,j<w1​i=1,j≥w1​wi​>1,j=1wi​=1,j=1wi​>j,i>1,j>1wi​≤j,i>1,j>1​

1.3 题目求解

在进行完题目分析后，我们用 MATLAB 和 Python 对题目进行编程求解：
MATLAB
函数实现：

function f = 01pack(v,w,W)
	m = length(v);
	dp = zeros(m,W);
	if w(1)<=W	% 初始化dp第一行
		dp(1,w(1):end) = v(1);
	end
	for i = 2:m	% 初始化dp第一列
		dp(i,1) = max([0,v(w(1:i)==1)]);
	end
	% i,j>1
	for i = 2:m
		for j= 2:W
			if w(i)>j
				dp(i,j) = dp(i-1,j);
			elseif w(i)==j
				dp(i,j) = max(dp(i-1,j),v(i));
			else
				dp(i,j) = max(v(i)+dp(i-1,j-w(i)),dp(i-1,j))
			end
		end
	end
	f = dp(m,W);
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

函数调用：

clear;clc;
v = [540, 200, 180, 350, 60, 150, 280, 450, 320, 120];
w = [6, 3, 4, 5, 1, 2, 3, 5, 4, 2];
W = 30;
tic;
f = dp01pack(v,w,W)
toc;
1
2
3
4
5
6
7

结果：

---

Python
函数实现：

def dp01pack(v, w, W):
    m = len(v)  # 物品个数
    # 初始化dp数组 m*M 元素全为0
    dp = [[0 for j in range(W)] for i in range(m)]
    # 处理第一行
    if w[0]<W:
        # 如果第一个物品重量小于W
        for j in range(w[0]-1,W):
            # 那么第一行从 j>=w[0]-1 之后，最大价值都为v[0]
            dp[0][j] = v[0]
    # 处理第一列
    for i in range(1, m):
        temp = [0]
        for k in range(i+1):
            if w[k]==1:
                temp.append(v[k])
        dp[i][0] = max(temp)
    # 处理剩下的部分
    for i in range(1, m):
        for j in range(1, W):
            if w[i]>(j+1):
                dp[i][j] = dp[i-1][j]
            elif w[i]==(j+1):
                dp[i][j] = max(v[i], dp[i-1][j])
            else:
                dp[i][j] = max(v[i]+dp[i-1][j-w[i]], dp[i-1][j])
    f = dp[-1][-1]
    return f
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

函数调用：

import time
v = [540, 200, 180, 350, 60, 150, 280, 450, 320, 120]
w = [6, 3, 4, 5, 1, 2, 3, 5, 4, 2]
W = 30
start = time.time()
print('01背包问题的最大价值为：')
f = dp01pack(v, w, W)
print(f)
end = time.time()
print('算法用时为(s)：')
print('%.8f' % (end-start))
1
2
3
4
5
6
7
8
9
10
11

结果：

---

1.4 得到选择物品的编号

在通过前面的步骤获得物品的最大价值后，我们来进一步思考：
如何得到选择物品的编号？

仍然是从 DP数组入手！

• 首先定位到最后一列（即第 $W$ 列，$W$ 为最大容量），然后顺序找到最大值位置对应的物品，此时这个物品就是我们选择的最后一个物品，若其编号为 $p$，重量为 $w_p$，则更新此时的 DP数组 为：$dp=dp(1:(p-1),1:(W-w_p))$，即只要原数组的前 $(p-1)\times (W-w_p)$ 部分，同时更新：$W=W-w_p$（将得到的编号 p 存入数组 IND 中）
• 若上一步得到的物品编号为 1 号，则直接输出所有得到的 IND（可以逆序输出），若不是，则重复前一步骤。

---

接下来我们分别用 MATLAB 和 Python 实现此需求：
MATLAB
函数实现：

function [f, IND] = dp01pack_ind(v,w,W)
	m = length(v);
	dp = zeros(m,W);
	if w(1)<=W	% 初始化dp第一行
		dp(1,w(1):end) = v(1);
	end
	for i = 2:m	% 初始化dp第一列
		dp(i,1) = max([0,v(w(1:i)==1)]);
	end
	% i,j>1
	for i = 2:m
		for j= 2:W
			if w(i)>j
				dp(i,j) = dp(i-1,j);
			elseif w(i)==j
				dp(i,j) = max(v(i), dp(i-1,j));
			else
				dp(i,j) = max(v(i)+dp(i-1,j-w(i)),dp(i-1,j));
			end
		end
	end
	f = dp(m,W);
    IND = [];
    if f>0
        temp = dp(:,W);
        while 1
            ind = find(temp==max(temp),1);
            W = W-w(ind);
            IND = [IND,ind];
            if ind>1 && W>0
                temp = dp(1:ind-1,W);
            else
                break
            end
        end
        IND = sort(IND);
    end
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

函数调用：

clear;clc;
v = [540, 200, 180, 350, 60, 150, 280, 450, 320, 120];
w = [6, 3, 4, 5, 1, 2, 3, 5, 4, 2];
W = 30;
% v = [11, 12, 10, 26, 14, 16];
% w = [3, 2, 2, 5, 1, 3];
% W = 10;
tic;
[f, IND] = dp01pack_ind(v,w,W)
toc;
1
2
3
4
5
6
7
8
9
10

结果：

---

Python
函数实现：

def dp01pack_ind(v, w, W):
    m = len(v)  # 物品个数
    # 初始化dp数组 m*M 元素全为0
    dp = [[0 for j in range(W)] for i in range(m)]
    # 处理第一行
    if w[0]<W:
        # 如果第一个物品重量小于W
        for j in range(w[0]-1,W):
            # 那么第一行从 j>=w[0]-1 之后，最大价值都为v[0]
            dp[0][j] = v[0]
    # 处理第一列
    for i in range(1, m):
        temp = [0]
        for k in range(i+1):
            if w[k]==1:
                temp.append(v[k])
        dp[i][0] = max(temp)
    # 处理剩下的部分
    for i in range(1, m):
        for j in range(1, W):
            if w[i]>(j+1):
                dp[i][j] = dp[i-1][j]
            elif w[i]==(j+1):
                dp[i][j] = max(v[i], dp[i-1][j])
            else:
                dp[i][j] = max(v[i]+dp[i-1][j-w[i]], dp[i-1][j])
    f = dp[-1][-1]
    # 输出编号
    IND = []
    if f>0:
        temp = []
        for i in dp:
            # 取出dp最后一列
            temp.append(i[W-1])
        while 1:
            ind = temp.index(max(temp))
            W = W-w[ind]
            IND.append(ind+1)
            if ind>0 and W>0:
                temp = []
                for i in dp[0:ind]:
                    temp.append(i[W-1])
            else:
                break
        IND.sort()
    return f, IND
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

函数调用：

import time
v = [540, 200, 180, 350, 60, 150, 280, 450, 320, 120]
w = [6, 3, 4, 5, 1, 2, 3, 5, 4, 2]
W = 30
start = time.time()
[f, IND] = dp01pack_ind(v, w, W)
print('01背包问题的最大价值为：')
print(f)
print('选择物品的编号为：')
print(IND)
end = time.time()
print('算法用时为(s)：')
print('%.8f' % (end-start))
1
2
3
4
5
6
7
8
9
10
11
12
13

结果：

---

二、硬币兑换的方案

2.1 题目描述

给定不同面值的 $m$ 种硬币 coins 和一个总金额 $S$，请编写一个函数来计算用这些硬币可以凑成总金额 $S$ 的方案数。（每种硬币数量是无限的，$S$ 以及 coins 中的元素都是正整数，且不考虑每种方案中硬币的顺序）
示例输入：
S=4, coins=[1, 2, 3]
示例输出：
4
解释：
有4种方案：[1, 1, 1, 1]，[1, 1, 2]，[2, 2] 和 [1, 3]

2.2 题目分析

定义原问题和子问题：
原问题：
能够使用所有面值的硬币来凑出总金额 S 的方案数。
子问题：
只能使用前 $i(i\le m)$ 种面值的硬币来凑出总金额 $j(j\le S)$ 的方案数。

定义状态：
根据子问题的定义，我们可以看出每种状态包含两个参数：第一个参数就是我们可以使用前多少种面值的硬币；第二个参数就是要凑出的总金额数。
因此，我们记 $f(i,j)$ 为只能使用前 $i(i\le m)$ 种面值的硬币来凑出总金额 $j(j\le S)$ 的方案数，当 $i=m$ 且 $j=S$ 时就是原问题的解。

寻找状态转移方程：
对于二维动态数组，我们还是先考虑边界条件：

• 当 $i=1$ 时，为 $f(1,j)$，即只使用第一种面值的硬币，设这种硬币面值为 $coin{s}_1$，那么若金额 $j$ 能被 $coin{s}_1$ 整除，那么就只有一种方案：用 $(j/coin{s}_1)$ 枚第一种面值的硬币；否则，则没有方案，用方程表示为：
  $$f(1,j)=\{\begin{array}{ll}1& j能被coin{s}_1整除\\ 0& j不能被coin{s}_1整除\end{array}$$
• 当 $j=1$ 时，为 $f(i,1)$，即用前 $i$ 种面值的硬币能凑出总金额为 1 的方案数，容易知道：若前 $i$ 种面值的硬币中有面值为 1 的硬币，则方案数 $f(i,1)$ 为1，否则为0.

接下来考虑一般情况，当 $i>1,j>1$ 时：

• 要凑的总金额 $j$ 小于第 $i$ 种硬币的面值，则第 $i$ 种硬币不会起到任何作用，则 $f(i,j)=f(i-1,j)$
• 要凑的总金额 $j$ 等于第 $i$ 种硬币的面值，可以选择是否使用：若我们使用第 $i$ 种硬币，那么只有 1 种方案，若不用，则为 $f(i-1,j)$。因此，最终为二者之和：$f(i,j)=f(i-1,j)+1$；
• 要凑的总金额 $j$ 大于第 $i$ 种硬币的面值，我们可以从 0 枚开始，依次增大第 $i$ 种硬币的选取量直到为 $k$，此时第 $i$ 种硬币凑的总金额大于或等于需要的总金额 $j$，那么可以得到：$f(i,j)=f(i-1,j-0\times coin{s}_i)+f(i-1,j-1\times coin{s}_i)+...+f(i-1,j-k\times coin{s}_i)$，经过化简得到：$f(i,j)=f(i-1,j)+f(i,j-coin{s}_i)$.

则得到一般情况下的状态转移方程为：
f ( i , j ) = { f ( i − 1 , j ) j − c o i n s i < 0 f ( i − 1 , j ) + 1 j − c o i n s i = 0 f ( i − 1 , j ) + f ( i , j − c o i n s i ) j − c o i n s i > 0 f(i,j)=

$$\begin{cases} f(i-1,j) & j-coins_{i}<0 \\ f(i-1,j)+1 & j-coins_{i}=0 \\ f(i-1,j)+f(i,j-coins_{i}) & j-coins_{i}>0 \end{cases}$$ f(i,j)=⎩⎪⎨⎪⎧​f(i−1,j)f(i−1,j)+1f(i−1,j)+f(i,j−coinsi​)​j−coinsi​<0j−coinsi​=0j−coinsi​>0​

2.3 题目求解

MATLAB
函数实现：

function [f,dp] = dp_coin(coins,S)
    coins = sort(coins);
    m = length(coins);
    dp = zeros(m,S);
    dp(1,:) = (mod(1:S,coins(1))==0);
    dp(:,1) = (coins(1)==1);
    for i = 2:m
        for j = 2:S
            if j-coins(i)<0
                dp(i,j) = dp(i-1,j);
            elseif j-coins(i)==0
                dp(i,j) = dp(i-1,j)+1;
            else
                dp(i,j) = dp(i-1,j)+dp(i,j-coins(i));
            end
        end
    end
    f = dp(m,S);
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

函数调用：

clear;clc;
coins = [2, 3, 5, 6];
S = 10;
tic;
[f,dp] = dp_coin(coins,S)
toc;
1
2
3
4
5
6

结果：

---

Python
函数实现：

def dp_coin(coins, S):
    coins.sort()
    m = len(coins)
    dp = [[0 for j in range(S)] for i in range(m)]
    for j in range(S):
        if (j+1)%coins[0]==0:
            dp[0][j] = 1
    for i in range(m):
        if coins[0]==1:
            dp[i][0] = 1
    for i in range(1, m):
        for j in range(1, S):
            if j+1-coins[i]<0:
                dp[i][j] = dp[i-1][j]
            elif j+1-coins[i]==0:
                dp[i][j] = dp[i-1][j]+1
            else:
                dp[i][j] = dp[i-1][j]+dp[i][j-coins[i]]
    f = dp[-1][-1]
    return f, dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

函数调用：

import time
coins = [2, 3, 5, 6]
S = 10
start = time.time()
[f,dp] = dp_coin(coins,S)
print('最终方案数为：')
print(f)
print('DP数组为：')
for i in dp:
    print(i)
end = time.time()
print('算法用时为(s)：')
print('%.8f' % (end-start))
1
2
3
4
5
6
7
8
9
10
11
12
13

结果：

---