問題描述：

?? ??? 有n種硬幣，面值分別為V1,V2...,Vn,每種都有無限多。給定非負整數(shù)S，可以選用多少個硬幣，使得面值之和恰好為S？輸出硬幣數(shù)目的最小值和最大值。0 <= n <= 100, 0 <= S <= 10000, 1 <= Vi <= S。

分析：
?? ??? 本題的本質(zhì)還是DAG上的路徑問題。我們把每種面值看作一個點，表示"還需要湊足的面值"，則初始狀態(tài)為S，目標狀態(tài)為0。若當前的狀態(tài)i，每使用一個硬幣j，狀態(tài)便轉(zhuǎn)移到i-Vj。這個模型和嵌套矩形一題類似，但也有些明顯的不同之處：嵌套矩形中并沒有確定路徑的起點和終點（可以把任意矩形放在第一個和最后一個），而本題的起點必須是S，終點必須是0。把終點固定之后"最短路"才是有意義的。在嵌套矩形中，最短序列顯然是空（如果不允許空的話，就是單個矩形，不管怎樣都是平凡的），而本題的最短路徑卻不是那么容易確定的。

?????? 接下來考慮"硬幣問題"。注意到最長路和最短路的求法是類似的，下面只考慮最長路。由于終點固定，d(i)的確切含義變?yōu)?#34;從節(jié)點i出發(fā)到節(jié)點0的最長路徑長度"。

下面是求最長路的代碼（錯誤的）：

int dp(int S)//錯誤 {int& ans=d[S];if(ans>=0) return ans;ans=0;for(int i=1;i<=n;i++)if(S>=V[i])ans=max(ans,dp(S-V[i])+1);return ans; } /*此代碼有一個致命的錯誤，即由于節(jié)點S不一定真的能到達節(jié)點0，所以需要用特殊的d[S]值表 示"無法到達"，但在上述代碼中，如果S根本無法繼續(xù)往前走，返回值是0，將被誤以為是"不能 走已經(jīng)到達終點"的意思。*/

正確的解法一：

int dp(int S) {int& ans=d[S];if(ans != -1) return ans;ans=-1<<30;for(int i=1;i<=n;i++)if(S>=V[i])ans=max(ans,dp(s-V[i])+1);return ans; } 注意：在記憶化搜索中，如果用特殊值表示"還沒有算過"，則必須將其和其他特殊值(如無解)區(qū)分開。

正確的解法二：

int dp(int S) {if(vis[S]) return d[S];vis[S]=1;int& ans=d[S];ans=-1<<30;for(int i=1;i<=n;i++)if(S>=V[i]){ans=max(ans,dp(S-V[i])+1);} return ans; } ?????? 盡管多了一個數(shù)組，但可讀性增強了許多：再也不用擔心特殊值之間的沖突了，在任何情況下，記憶化搜索的初始化都可以用memset(vis,0,sizeof(vis))執(zhí)行。

????? 本題要求最小、最大兩個值，記憶化搜索就必須寫兩個。在這種情況下，還是遞推來得更加方便（此時需注意遞推的順序）：

min[0]=max[0]=0; for(int i=1;i<=n;i++) {min[i]=INF; max[i]=-INF; } for(int i=1;i<n;i++)for(int j=1;j<=v;j++)if(i>=V[j]){min[i]=min(min[i],min[i-V[j]]+1);max[i]=max(max[i],max[i-V[j]]+1);} printf("%d %d\n",min[S],max[S]);

完整代碼：

#include "stdio.h" #define INF 1<<30 #define maxn 100+10 int V[maxn],n; int min[maxn],max[maxn];inline int Min(int a,int b){return a<b?a:b;} inline int Max(int a,int b){return a>b?a:b;}//打印可行的方案 void print_ans(int* d,int S){for(int i=1;i<=n;i++){if(S>=V[i] && d[S]==d[S-V[i]]+1){printf("%d ",V[i]);print_ans(d,S-V[i]);break;}} }int main() {int S;//輸入面值S和面值的種數(shù)n while(~scanf("%d%d",&S,&n)){ for(int i=1;i<=n;i++){scanf("%d",&V[i]);}max[0]=0; min[0]=0;for(int i=1;i<=S;i++){min[i]=INF; max[i]=-INF;}//遞推實現(xiàn) for(int i=1;i<=S;i++){for(int j=1;j<=n;j++){if(i>=V[j]){min[i]=Min(min[i],min[i-V[j]]+1);max[i]=Max(max[i],max[i-V[j]]+1);}}}print_ans(min,S); printf(" min\n");print_ans(max,S); printf(" max\n");printf("min:%d max:%d\n",min[S],max[S]); }return 0; }

總結

以上是生活随笔為你收集整理的硬币问题——固定终点的最长路和最短路的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。