第八章 動態(tài)規(guī)劃 3 AcWing 1554. 找更多硬幣 原題鏈接

AcWing 1554. 找更多硬幣

創(chuàng)新新互聯(lián)，憑借十余年的成都網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)經(jīng)驗，本著真心·誠心服務(wù)的企業(yè)理念服務(wù)于成都中小企業(yè)設(shè)計網(wǎng)站有上1000+案例。做網(wǎng)站建設(shè)，選創(chuàng)新互聯(lián)建站。算法標簽

DP 背包問題

思路

經(jīng)典01背包問題

閆氏DP分析法
狀態(tài)表示

狀態(tài)初始化

狀態(tài)計算

狀態(tài)轉(zhuǎn)移方程式

要求字典序最小，因此先存硬幣面額到數(shù)組再降序排列，保證逆序得到的是升序的方案序列

代碼

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include#define int long long
#define x first
#define y second
#define ump unordered_map
#define ums unordered_set
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i=b;--i)
using namespace std;
typedef pairPII;
const int N=10005, M=105, INF=0x3f3f3f3f3f3f3f3f;
const double Exp=1e-8;
//int t, n, m, cnt, ans;
int n, m, w[N];
bool f[N][M];
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	f[0][0]=true;
	n=rd(), m=rd();
	rep(i, 1, n+1){
	    w[i]=rd();
	}
	sort(w+1, w+n+1, greater());
	rep(i, 1, n+1){
	    rep(j, 0, m+1){
	        f[i][j]=f[i-1][j];
	        if(j>=w[i]){
	            f[i][j]|=f[i-1][j-w[i]];
	        }
	    }
	}
	if(!f[n][m]){
	    puts("No Solution");
	}else{
	    bool fi=true;
	    while(n){
	        if(m>=w[n]&&f[n-1][m-w[n]]){
	            if(fi){ 
	                fi=false;
	            }else{
	                printf(" ");
	            }
	            printf("%lld", w[n]);
	            m-=w[n];
	        }
	        n--;
	    }
	}
	return 0;
}

參考文獻

AcWing 1554. 找更多硬幣（PAT甲級輔導課）y總視頻講解

原創(chuàng)不易
轉(zhuǎn)載請標明出處
如果對你有所幫助 別忘啦點贊支持哈

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當前文章：第八章動態(tài)規(guī)劃3AcWing1554.找更多硬幣-創(chuàng)新互聯(lián)
瀏覽地址：http://aaarwkj.com/article28/iddjp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設(shè)、App開發(fā)、虛擬主機、電子商務(wù)、定制網(wǎng)站、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)