HDOJ(HDU).2844 Coins (DP 多重背包+二進制優化)

2019-11-08 01:45:36

字體：大中小

來源：轉載

供稿：網友

HDOJ(HDU).2844 Coins (DP 多重背包+二進制優化)

題意分析

先把每種硬幣按照二進制拆分好，然后做01背包即可。需要注意的是本題只需要求解可以湊出幾種金錢的價格，而不需要輸出種數。因此用0表示不可以，1表示可以。最后對dp數組掃描一遍即可。

代碼總覽

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define nmax 100000#define nn 105#define INIT(x,y) memset(x,y,sizeof(x))using namespace std;int a[nn],c[nn];int PRi[nmax],num[nmax],dp[nmax];int main(){ //freopen("in.txt","r",stdin); int n,m; while(scanf("%d%d",&n,&m) && n){ INIT(dp,0); INIT(a,0);INIT(c,0); INIT(pri,0);INIT(num,0); for(int i = 1; i<=n;++i) scanf("%d",&a[i]); for(int i = 1; i<=n;++i) scanf("%d",&c[i]); int cnt = 0; for(int k =1 ;k<=n ;++k){ for(int i =1; i<=c[k];i*=2){ pri[cnt] = i * a[k]; num[cnt++] = i * 1; c[k]-=i; } if(c[k]>0){ pri[cnt] = c[k] * a[k]; num[cnt++] = c[k]; } } dp[0] = 1; for(int i = 0; i<=cnt;++i){ for(int j = m; j>=pri[i]; --j){ //dp[j] = max(dp[j],dp[j-pri[i]]+1); if(dp[j-pri[i]]) dp[j] =1; }// for(int i =0;i<=m;++i) printf(" %3d",dp[i]);// printf("/n"); }// for(int i =1;i<=m;++i) printf(" %3d",i);// printf("/n");//// printf("%d/n"); int ans = 0; for(int i = 1;i<=m;++i) if(dp[i] == 1) ans++; printf("%d/n",ans); } return 0;}

上一篇：面向對象之繼承、super和this的比較

下一篇：算法提高拿糖果線性DP