//給出6枚不同面值(在1到100之間)的硬幣，通過 加減 湊出1到100的錢數，我們關心的是最少要用到幾枚硬幣，

//最后求出平均值，并找出其中最大值

BFS #include<iostream> //BFS最短路搜索
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
int euro[20],f[200],vis[200];
int main()
{
int cases;
cin>>cases;
while(cases--)
{
for(int i=1;i<=6;++i)
{
cin>>euro[i];
euro[i+6]=-euro[i];
}
memset(vis,0,sizeof(vis));
queue<int> col;
col.push(0);
while(!col.empty())
{
int fro=col.front();
col.pop();
for(int i=1;i<=12;++i)
{
int u=fro+euro[i];
if(u>0&&u<200&&vis[u]==0) //因為允許減,所以一個數可以由超過100的數減另一個數得到。由于The last number is less than 100.考慮減去99的情況,故 u 的最大值取 199, 即 199-99=100
{
f[u]=f[fro]+1; //最短路搜索,因為是寬搜,所以只要搜索到u,則f[u]肯定是組成幣值u所需的最小貨幣數目
vis[u]=1;
col.push(u);
}
}
}
double ave=0;
for(int i=1;i<=100;++i)
ave+=f[i];
printf("%.2f %d\n",ave/100,*max_element(f+1,f+101));
}
return 0;
}

完全背包 //參考 poj 3260 The Fewest Coins

#include<iostream> //完全背包
#include<stdio.h>
#include<algorithm>
using namespace std;
int main()
{
int cases,euro[10],dp[20000],maxn;
cin>>cases;
while(cases--)
{
for(int i=1;i<=6;++i)
cin>>euro[i];
maxn=euro[5]*euro[5]+100; //上界
fill(dp,dp+maxn,-1);
dp[0]=0;
for(int i=1;i<=6;++i) // 加運算
{
for(int j=euro[i];j<=maxn;++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);
}
}
for(int i=1;i<=6;++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);
}
}
double ave=0;
for(int i=1;i<=100;++i)
ave+=dp[i];
printf("%.2f %d\n",ave/100,*max_element(dp+1,dp+101));
}
return 0;
}

轉載于:https://www.cnblogs.com/mjc467621163/archive/2011/07/11/2103305.html

總結

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

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