題目描述

Farmer John has gone to town to buy some farm supplies. Being a very efficient man, he always pays for his goods in such a way that the smallest number of coins changes hands, i.e., the number of coins he uses to pay plus the number of coins he receives in change is minimized. Help him to determine what this minimum number is.

FJ wants to buy T (1 ≤ T ≤ 10,000) cents of supplies. The currency system has N (1 ≤ N ≤ 100) different coins, with values V1, V2, ..., VN (1 ≤ Vi ≤ 120). Farmer John is carrying C1 coins of value V1, C2 coins of value V2, ...., and CN coins of value VN (0 ≤ Ci ≤ 10,000). The shopkeeper has an unlimited supply of all the coins, and always makes change in the most efficient manner (although Farmer John must be sure to pay in a way that makes it possible to make the correct change).

農(nóng)夫John想到鎮(zhèn)上買些補給。為了高效地完成任務(wù)，他想使硬幣的轉(zhuǎn)手次數(shù)最少。即使他交付的硬 幣數(shù)與找零得到的的硬幣數(shù)最少。 John想要買T(1<=T<=10000)樣?xùn)|西（2017-7-20 管理員注：這個翻譯有問題，實際為要買價值為T的東西）。有N(1<=n<=100)種貨幣參與流通，面值分別為V1,V2..Vn (1<=Vi<=120)。John有Ci個面值為Vi的硬幣(0<=Ci<=10000)。我們假設(shè)店主有無限多的硬幣， 并總按最優(yōu)方案找零。

輸入輸出格式

輸入格式：

?

Line 1: Two space-separated integers: N and T.

Line 2: N space-separated integers, respectively V1, V2, ..., VN coins (V1, ...VN)

Line 3: N space-separated integers, respectively C1, C2, ..., CN

?

輸出格式：

?

Line 1: A line containing a single integer, the minimum number of coins involved in a payment and change-making. If it is impossible for Farmer John to pay and receive exact change, output -1.

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 3 70 5 25 50 5 2 1 輸出樣例#1：?復(fù)制 3

說明

Farmer John pays 75 cents using a 50 cents and a 25 cents coin, and receives a 5 cents coin in change, for a total of 3 coins used in the transaction.

?

思路比較簡單

對john做一次多重背包

對店主做一次完全背包(然而不會寫代碼)

多重背包用二進(jìn)制優(yōu)化

另外，本蒟蒻不怎么懂為什么枚舉上界是所有面值相乘再加T，

剛開始寫面值乘數(shù)量死活RE QWQ...

?

#include<cstring> #include<cstdio> #include<cstdlib> #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++) #define min(a,b) (a<b?a:b) #define max(a,b) (a<b?b:a) char buf[1<<22],*p1=buf,*p2=buf; //#define int long long using namespace std; const int MAXN=5*1e6+10,INF=1e8+10; inline int read() {char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } int f[MAXN];//恰好為i時的最小花費 int g[MAXN];//完全背包 int val[MAXN],num[MAXN]; int N,T,limit=0; int main() {#ifdef WIN32freopen("a.in","r",stdin);#endifN=read();T=read();for(int i=1;i<=N;i++) val[i]=read();for(int i=1;i<=N;i++) num[i]=read(),limit+=val[i]*val[i];memset(f,0x3f,sizeof(f));memset(g,0x3f,sizeof(g));g[0]=0;f[0]=0;for(int i=1;i<=N;i++)for(int j=val[i];j<=limit;j++)g[j]=min(g[j],g[j-val[i]]+1);for(int i=1;i<=N;i++) {for(int k=1;k<=num[i];k<<=1) {for(int j=limit;j>=val[i]*k;j--)f[j]=min(f[j],f[j - val[i]*k]+k);num[i]-=k;} if(num[i])for(int j=limit;j>=val[i]*num[i];j--) f[j]=min(f[j],f[j - val[i]*num[i]]+num[i]); }int ans=INF;for(int i=T;i<=limit;i++)ans=min(ans,f[i]+g[i-T]);ans==INF?printf("-1"):printf("%d",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zwfymqz/p/8782645.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P2851 [USACO06DEC]最少的硬币The Fewest Coins(完全背包+多重背包)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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