兩個動態規劃的經典問題

硬幣問題

問題描述：設有n種不同面值的硬幣，各硬幣的面值存於陣列T[1：n]中。現要用這些面值的硬幣來找錢。可以使用的各種面值的硬幣個數存於陣列Coins[1:n]中。

對任意錢數0≦m≦20001，設計一個用最少硬幣找錢m的方法。

演演算法設計：對於給定的1≦n≦10，硬幣面值陣列T和可用使用的各種面值的硬幣個數陣列Coins，以及錢數m，0≦m≦20001，計算找錢m的最少硬幣數。

我們再回想一下實現動態規劃的前提：

• 最佳化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最佳化原理。
• 無後效性：即某階段狀態一旦確定，就不受這個狀態以後決策的影響。也就是說，某狀態以後的過程不會影響以前的狀態，只與當前狀態有關；
• 有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到（該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃演演算法同其他演演算法相比就不具備優勢）。

在做這道題之前，我們先來看一個樣例：

問題描述

假設有 1 元，3 元，5 元的硬幣若干（無限），現在需要湊出 11 元，問如何組合才能使硬幣的數量最少？

問題分析

乍看之下，我們簡單的運用一下心算就能解出需要 2 個 5 元和 1 個 1 元的解。當然這裡只是列出了這個問題比較簡單的情況。當硬幣的幣制或者種類變化，並且需要湊出的總價值變大時，就很難靠簡單的計算得出結論了。貪婪演演算法可以在一定的程度上得出較優解，但不是每次都能得出最優解。

這裡運用動態規劃的思路解決該問題。按照一般思路，我們先從最基本的情況來一步一步地推導。

我們先假設一個函數 d(i) 來表示需要湊出 i 的總價值需要的最少硬幣數量。

1.當 i = 0 時，很顯然我們可以知道 d(0) = 0。因為不要湊錢了嘛，當然也不需要任何硬幣了。注意這是很重要的一步，其後所有的結果都從這一步延伸開來。
2.當 i = 1 時，因為我們有 1 元的硬幣，所以直接在第 1 步的基礎上，加上 1 個 1 元硬幣，得出 d(1) = 1。
3.當 i = 2 時，因為我們並沒有 2 元的硬幣，所以只能拿 1 元的硬幣來湊。在第 2 步的基礎上，加上 1 個 1 元硬幣，得出 d(2) = 2。
4.當 i = 3 時，我們可以在第 3 步的基礎上加上 1 個 1 元硬幣，得到 3 這個結果。但其實我們有 3 元硬幣，所以這一步的最優結果不是建立在第 3 步的結果上得來的，而是應該建立在第 1 步上，加上 1 個 3 元硬幣，得到 d(3) = 1。

...

接著就不再舉例了，我們來分析一下。可以看出，除了第 1 步這個看似基本的公理外，

其他往後的結果都是建立在它之前得到的某一步的最優解上，加上 1 個硬幣得到。

得出：d(i) = d(j) + 1

這裡 j < i。通俗地講，我們需要湊出 i 元，就在湊出 j 的結果上再加上某一個硬幣就行了。

那這裡我們加上的是哪個硬幣呢。嗯，其實很簡單，把每個硬幣試一下就行了：

假設最後加上的是 1 元硬幣，那 d(i) = d(j) + 1 = d(i - 1) + 1。
假設最後加上的是 3 元硬幣，那 d(i) = d(j) + 1 = d(i - 3) + 1。
假設最後加上的是 5 元硬幣，那 d(i) = d(j) + 1 = d(i - 5) + 1。

我們分別計算出 d(i - 1) + 1，d(i - 3) + 1，d(i - 5) + 1 的值，取其中的最小值，即為最優解，也就是 d(i)。

最後公式：

int main() {
    int n, m, dp[20002];
    cin >> n;//輸入硬幣種類
    int value[n + 1], coins[n + 1];
    for (int i = 1; i <= n; i++)
        cin >> value[i] >> coins[i];//分別輸入面值與數量
    cin >> m;//最後找錢m
    for (int i = 1; i < 20002; i++)
        dp[i] = 1000000;//一維陣列儲存結果初定義
    dp[0] = 0;
    
    
    for (int i = 1; i <= n; i++)//面值種類
        for (int j = 1; j <= coins[i]; j++)//面值數量
            for (int k = m; k >= value[i]; k--)
                dp[k] = min(dp[k - value[i]] + 1, dp[k]);//核心（先找面值大的硬幣，）

    
    cout << (dp[m] < 1000000 ? dp[m] : -1) << endl;//問題無解輸出-1
    return 0;
}

揹包問題

5個物體，重量分別為3，5，7，8，9，價值分別為4，6，7，9，10，揹包容量為22，物體不能分割，求裝入揹包物體最大價值，寫出求解過程。

//題目：
//求解下面的揹包問題。有5個體積是3，5，7，8和9，價值為4，6，7，9和10的物品，揹包的容量是22。
#include<iostream>
using namespace std;
#define NUM 5 //物體的個數
#define CAPCITY 22 //揹包的容量
int main(){
	//初始化每個物體的體積以及價值，注意陣列第一個元素是0
    int volume[CAPCITY+1]={0,3,5,7,8,9};
	int value[NUM+1]={0,4,6,7,9};
	//新建一個二維表用於儲存每一步的結果
	int result[NUM+1][CAPCITY+1];
 
	//初始化二維結果表，這裡的初始化是指記錄每次選擇(每一步)的最大價值，注意這裡的選擇不是窮舉啊，演演算法的邏輯不清楚的話可以看
    //演演算法圖解
	for(int i=0;i<=NUM;i++){result[i][0]=0;}
	for(int j=0;j<=CAPCITY;j++){result[0][j]=0;}
	for(int i=1;i<=NUM;i++){
		for(int j=1;j<=CAPCITY;j++){
			result[i][j]=result[i-1][j];
			if(volume[i]<=j){
				result[i][j]=max(result[i][j],result[i-1][j-volume[i]]+value[i]);
			}
		}
	}
    //將包含選擇結果的表列印下來
	for(int k=0;k<=NUM;k++){
		for(int l=0;l<=CAPCITY;l++){
			cout<<result[k][l];
			if(result[k][l]>9)
				cout<<' ';
			else
				cout<<"  ";
		}
		cout<<endl;
	}
	cout<<"由上表可知，揹包內可裝下的物品的最大價值是："<<result[NUM][CAPCITY]<<endl;
    system("pause");
	return 0;
}