題目描述：

? ? 有若干張郵票，要求從中選取最少的郵票張數(shù)湊成一個(gè)給定的總值。
? ? 如，有1分，3分，3分，3分，4分五張郵票，要求湊成10分，則使用3張郵票：3分、3分、4分即可。

輸入：

??? 有多組數(shù)據(jù)，對(duì)于每組數(shù)據(jù)，首先是要求湊成的郵票總值M，M<100。然后是一個(gè)數(shù)N，N〈20，表示有N張郵票。接下來(lái)是N個(gè)正整數(shù)，分別表示這N張郵票的面值，且以升序排列。

輸出：

????? 對(duì)于每組數(shù)據(jù)，能夠湊成總值M的最少郵票張數(shù)。若無(wú)解，輸出0。

樣例輸入：

10 5 1 3 3 3 4

樣例輸出：

3

算法分析

動(dòng)態(tài)規(guī)劃問(wèn)題，和之后的兩船載物、今年暑假不AC、招聘會(huì)、熱愛生活（發(fā)大米）、DOTA等均為同一類型題目，背包問(wèn)題。

在該題中采用動(dòng)態(tài)規(guī)劃，跟0-1背包問(wèn)題一樣，知道每個(gè)郵票的值，求恰好滿足value的最小個(gè)數(shù)，只是這里求的是個(gè)數(shù)不是最大value，計(jì)算從1到m面值的最小郵票數(shù) 。更新如下

for(int j = m;j>=num[i];j--){ //must from m to num[i] dp[j] = std::min(dp[j],dp[j-num[i]]+1);
dp[j]表示總值是j時(shí)，需要的郵票個(gè)數(shù)，郵票i分兩種情況：

1、放進(jìn)去 ?則郵票個(gè)數(shù)?dp[j-num[i]]+1

2、不放進(jìn)去 則郵票個(gè)數(shù)?dp[j]

所以在dp[i][j]時(shí)的最優(yōu)結(jié)構(gòu)是 dp[i][j]=min(dp[i-1][j],dp[i][j-num[i]+1,轉(zhuǎn)換為一維矩陣就是dp[j]=min(dp[j],dp[j-num[i]]+1)

因?yàn)槭乔『檬悄骋粋€(gè)值，初始化時(shí)，dp[0]=0, ?dp[1......V]=INT_MIN;

#include <stdio.h> #define INF 1000 int main() {int f[1000]; // 郵票價(jià)值為i時(shí)的個(gè)數(shù) int i,j,k;int M,N;int v[21];while(scanf("%d %d",&M,&N)!=EOF){for(i=1;i<101;i++) f[i]=INF; // 初始化 for(i=1;i<=N;i++) scanf("%d",&v[i]); // 郵票大小 f[0]=0;for(i=1;i<=N;i++) // 循環(huán)每個(gè)郵票 for(j=M;j>=0;j--) // 循環(huán)總價(jià)值 if(j-v[i]>=0) f[j] = f[j-v[i]]+1 > f[j] ? f[j] : f[j-v[i]]+1; // 取f[j-v[i]]+1和f[j]的最小值 if(f[M]>=101) printf("0\n");else printf("%d\n",f[M]);}return 0; }或者
void minNum(int m,int n){int *dp = new int[m+1];dp[0] = 0;for(int i = 1;i<=m;i++)dp[i] = INF;int *num = new int[n];for(int i = 0;i<n;i++)std::cin>>num[i];for(int i = 0;i<n;i++){for(int j = m;j>=num[i];j--){ //must from m to num[i]dp[j] = std::min(dp[j],dp[j-num[i]]+1);}}if(dp[m]<INF)std::cout<<dp[m]<<std::endl;elsestd::cout<<0<<std::endl; }

總結(jié)

以上是生活随笔為你收集整理的最小邮票数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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