背包 要么 BFS

意大利是說給你幾個基本的貨幣，組成 1~100 所有貨幣，使用基本上的貨幣量以最小的。

出口 用法概率。和最大使用量。

能夠BFS 有可能 。

只是記得數(shù)組開大點。 可能會出現(xiàn) 100 = 99+99 -98 的情況。

背包是先做一個全然背包，求得最少可能由多少相加。

然后做一個 01背包，看是否能被 減。

背包：

#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; int dp[10002];int value[7];int main() {int t;scanf("%d",&t);while(t--){int m=10001;for(int i=0; i<6; i++)scanf("%d",&value[i]);for(int i=1; i<m; i++)dp[i]=10001;dp[0]=0;for(int i=0; i<6; i++){for(int j=value[i]; j+value[i]<m; j++){dp[j]=min(dp[j-value[i]]+1,dp[j]); // printf("%d :%d==\n",j,dp[j]);}}for(int i=0; i<6; i++){for(int j=m-value[i]; j>0; j--){dp[j]=min(dp[j+value[i]]+1,dp[j]); // printf("%d :%d==\n",j,dp[j]);}}double ans=0;int maxn=0;for(int i=1; i<=100; i++){ // printf("%d : %d\n",i,dp[i]);ans+=dp[i];maxn=max(maxn,dp[i]);}printf("%.2f %d\n",ans/100.0,maxn);} }

BFS：

#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; struct lx {int ans,lv; }; int ans[2051]; int value[7]; void bfs() {queue<lx>q;bool vis[2051];memset(vis,0,sizeof(vis));lx now,tmp;tmp.ans=0,tmp.lv=0;q.push(tmp);vis[0]=1;while(!q.empty()){tmp=q.front();q.pop();ans[tmp.ans]=tmp.lv;for(int i=0;i<6;i++){int num1=tmp.ans+value[i];int num2=tmp.ans-value[i];now.lv=tmp.lv+1;if(!vis[num1]&&num1>0&&num1<2000){vis[num1]=1;now.ans=num1;q.push(now);}if(!vis[num2]&&num2>0&&num2<2000){vis[num2]=1;now.ans=num2;q.push(now);}}} } int main() {int t;scanf("%d",&t);while(t--){for(int i=0; i<6; i++)scanf("%d",&value[i]);bfs();double an=0;int maxn=0;for(int i=1;i<=100;i++){an+=ans[i];maxn=max(maxn,ans[i]); // printf("%d : %d\n",i,ans[i]);}printf("%.2f %d\n",an/100,maxn);} }

版權(quán)聲明：本文博客原創(chuàng)文章。博客，未經(jīng)同意，不得轉(zhuǎn)載。

總結(jié)

以上是生活随笔為你收集整理的POJ 1252 Euro Efficiency的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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