動态規劃學習筆記1-硬币找零 2021.3.1

題意描述：

假設有幾種硬币，如1、3、5，并且數量無限。請找出能夠組成某個數目的找零所使用最少的硬币數。

輸入格式：

第一行兩個整數數t，n，表示總金額和面值總數；

第二行n個整數a1,a2…an，其中ai表示第i種硬币的面值。

輸出格式：

最少硬币總數。如果無解，輸出-1。

樣例輸入：

15 3

1 11 5

樣例輸出：

3

思路分析：

1.暴力搜尋

  将最小值設定為一個很大的數INF，然後設立一個遞歸函數dfs(int amount)求解即可，其中amount代表目前待找錢的數額，遞歸使用dfs(amount-mz[i])，其中mz[i]代表第i種硬币的面值，遞歸結束條件為amount ==0，＜0代表目前面值無解。全部結束後如果最小值仍為INF則無解。

此解法會造成大量重複計算，因而耗費時間。

代碼就不貼了。

2.記憶化搜尋

  可以用記憶化搜尋節省時間。

  設立記憶數組vis，開始全部初始化為-1，遞歸函數改為int型，amount ==0時就不用找了，傳回0，小于0時傳回-1，此時代表目前面值無解，minn仍為INF，記憶數組中對應項仍為-1。否則就要改變。

代碼：

#include <cstdio>
#include <algorithm>
#define M 51 //硬币最多50種
#define MAX_VALUE 10001 //金額最多1萬
#define INF 0xffff0
using namespace std;
int mz[M],n,cnt=0;
int vis[MAX_VALUE];
int dfs(int amount){
	int minn=INF; //必須為局部變量，防止改變
    if(amount<0)
        return -1;
    if(amount==0){
        return 0;
    }
    if(vis[amount]>=0)
        return vis[amount];//記憶化搜尋
    for(int i=0;i<n;i++){
        int k=dfs(amount-mz[i]);
        if(k!=-1)
        	minn=min(minn,k+1); //傳回-1證明目前金額沒有符合題意的解，minn會維持為INF友善下面傳回，另：若有解要加上目前硬币
			//另：minn不能設為-1
    }
    if(minn!=INF)
    	vis[amount]=minn;  //必須在外面傳回，否則循環執行一次就會終止，另外，如果minn為INF就證明目前金額沒有符合題意的解，無需更新vis[amount]
    return vis[amount];
}

int main(){
    int t;
    fill(vis,vis+MAX_VALUE,-1); //一開始将所有值設為-1，如果沒有解直接輸出也是正确的
    scanf("%d%d",&t,&n);
    for(int i=0;i<n;i++)
        scanf("%d",&mz[i]);
    dfs(t);
    printf("%d",vis[t]);
    return 0;
}
           

3.動态規劃

上面的遞歸儲存了求得的值，屬于動态規劃的思想。但仍可以将遞歸改寫為遞推求解。

按照個人了解，遞歸是“自頂向下”将原問題“分解”，如本題中将總額t分解直至0，而動态規劃則是“自底向上”将子問題“合成”為原問題的解。

#include <cstdio>
#include <cmath>
#include <algorithm>
#define M 51 //硬币最多50種
#define MAX_VALUE 10001 //金額最多1萬
#define MAX 0xffff0
using namespace std;
int mz[M],k,cost[MAX_VALUE]; //mz代表面值，cost[i]為找零i元需要的硬币數最小值
void change(int x,int *used) {
    int i,j,k=-1;
    fill(cost,cost+M,MAX);
    int sum=0; //從1開始循環
    for(i=1; i<=x; i++) { //要找的錢數
        for(j=0; j<k; j++) {
            if(i>=mz[j]) {
                k=cost[i];
                cost[i]=min(cost[i],cost[i-mz[j]]+1); //狀态轉移方程，要+1選上目前物品
                if(k!=cost[i]) {
                    used[i]=mz[j];
                }
            }
        }
    }
    return cost;
}

int main() {
    int n,i/*,used[1000]= {0}*/; //used[i]為找零i最後找出的錢
    scanf("%d",&n);
//    int m=n;
	for(i=1;i<=n;i++)
		scanf("%d",&mz[i]);
    if(cost[n]==MAX)
        printf("-1");
    else {
        printf("%d",cost[n]);
/*        while(m>0) { //輸出找零金額
            printf("%d ",used[m]);
            m-=used[m];
        }
        printf("\n");*/
    }
    return 0;
}
           

明日計劃：0-1背包，完全背包問題