http://poj.org/problem?id=1276

題意 ： 給你一個目標錢數，再給你錢幣的種數和錢幣的面值，讓你用這些錢湊出不大于目標錢數的錢然后輸出這個最接近且不大于目標錢數的錢。

思路 ： 背包問題，還是多重背包，就是找到公式然后注意一下數組大小，還要小小的注意一下，因為那個錢數的范圍挺大的，做一個小小的優化吧也算是 。

代碼 ：?

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std ;
struct node
{int n;int d ;
} cas[21] ;
int main()
{int cash ;int n,ch[110000] ;while(scanf("%d",&cash)!=EOF){int m;cin>>n ;for(int i = 0 ; i < n ; i++)cin>>cas[i].n >>cas[i].d ;memset(ch,0,sizeof(ch)) ;ch[0] = 1 ;/*ch是標記數組，也可以說是一個小小的優化吧，再已經標記的基礎上繼續往上加，不用再從頭開始加了,否則會超時*/int maxm = 0 ;//for循環從每種紙幣開始，再對錢數進行枚舉，每種紙幣又有n張for(int i = 0 ; i < n ; i++)for(int j = maxm ; j >= 0 ; j--)if(ch[j])for(int k = 1 ; k <= cas[i].n ; k++){m = j + cas[i].d * k;if(m > cash)break ;ch[m] = 1 ;if(m > maxm)maxm = m ;}cout<<maxm<<endl ;}return 0 ;
}

View Code

?

轉載于:https://www.cnblogs.com/luyingfeng/p/3365306.html

總結

以上是生活随笔為你收集整理的POJ1276Cash Machine的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。