//poj 3260 The Fewest Coins

/*

題意：John帶了n種幣值Vi的確定數量Ci的硬幣,而shopkeeper的硬幣無限多.
給出T，求John支付的硬幣數目加上售貨員找零的硬幣數目的最小值。如果無法支付T，輸出-1
支付時硬幣數量有限制，為多重背包問題. 找零時硬幣數量無限制，為完全背包問題
*/


#include<iostream> //多重背包和完全背包
using namespace std;
int main()
{
int n,t,euro[110],num[110],dp[30000],maxn;
cin>>n>>t;
int mx=0;
for(int i=1;i<=n;++i)
{
cin>>euro[i];
mx=max(mx,euro[i]);
}
maxn=mx*mx+t; //上界
for(int i=1;i<=n;++i)
cin>>num[i];
fill(dp,dp+maxn+1,-1);
dp[0]=0;

//John付錢 多重背包，通過二進制方法轉化為01背包
for(int i=1;i<=n;++i)
{
int k=1,s=num[i];
while(s>=k)
{
for(int j=maxn;j>=euro[i]*k;--j)
if(dp[j-euro[i]*k]!=-1)
{
if(dp[j]==-1)
dp[j]=dp[j-euro[i]*k]+k; //注意是 +k
else
dp[j]=min(dp[j],dp[j-euro[i]*k]+k);
}
s-=k;k*=2;
}
for(int j=maxn;j>=euro[i]*s;--j)
if(dp[j-euro[i]*s]!=-1)
{
if(dp[j]==-1)
dp[j]=dp[j-euro[i]*s]+s;
else
dp[j]=min(dp[j],dp[j-euro[i]*s]+s);
}
}

//shopkeeper找錢 完全背包
for(int i=1;i<=n;++i)
{
for(int j=maxn-euro[i];j>0;--j) //因為是減,所以要逆序循環
if(dp[j+euro[i]]!=-1)
{
if(dp[j]==-1)
dp[j]=dp[j+euro[i]]+1;
else
dp[j]=min(dp[j],dp[j+euro[i]]+1);
}
}

cout<<dp[t]<<endl;
return 0;
}

/*

上界為：T+maxValue^2，其中maxValue為最大硬幣面值。
證明：反證法。假設存在一種支付方案，John給的錢超過T+maxValue^2， 則售貨員找零超過maxValue^2，找的硬幣數目超過maxValue個，將其看作一數列，求前n項和sum(n)，
根據鴿巢原理，至少有兩 個對maxValue求模的值相等，假設為sum(i)和sum(j),i<j，則i+1...j的硬幣面值和為maxValue的倍數，
同理，John給的錢中也有 一定數量的硬幣面值和為maxValue的倍數，
則這兩堆硬幣可用數量更少的maxValue面值硬幣代替，產生更優方案。

*/

　　

轉載于:https://www.cnblogs.com/mjc467621163/archive/2011/08/23/2151020.html

總結

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

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