算法提高 貪吃的大嘴 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB 提交此題 問(wèn)題描述 有一只特別貪吃的大嘴,她很喜歡吃一種小蛋糕,而每一個(gè)小蛋糕有一個(gè)美味度,而大嘴是很傲嬌的,一定要吃美味度和剛好為m的小蛋糕,而且大嘴還特別懶,她希望通過(guò)吃數(shù)量最少的小蛋糕達(dá)到這個(gè)目的.所以她希望你能設(shè)計(jì)一個(gè)程序幫她決定要吃哪些小蛋糕. 輸入格式 先輸入一行包含2個(gè)整數(shù)m、n,表示大嘴需要吃美味度和為m的小蛋糕,而小蛋糕一共有n種,下面輸入n行,每行2個(gè)整數(shù),第一個(gè)表示該種小蛋糕的美味度,第二個(gè)表示蛋糕店中該種小蛋糕的總數(shù) 輸出格式 輸出一行包含一個(gè)整數(shù)表示大嘴最少需要吃的小蛋糕數(shù)量,若大嘴無(wú)法通過(guò)吃小蛋糕達(dá)到m的美味度和,則輸出”><“. 樣例輸入 10 2 4 1 2 10 樣例輸出 4 樣例輸入 10 2 4 1 7 3 樣例輸出
< 數(shù)據(jù)規(guī)模和約定 m ≤ 20000,小蛋糕總數(shù)量≤50.
簡(jiǎn)單背包
搜索直接超時(shí)，但是m的數(shù)量為2w，n最大為50，所以最多運(yùn)算100w次 所以背包是很理想的算法選擇
#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#include <cmath>#include <map>using namespace std;int d[505];int dp[50000],tag[50000];int m,n,mins;const int mod=1000000;void bfs(int n){ memset(dp,1,sizeof(dp)); tag[0]=1; dp[0]=0; dp[m]=mod; for(int i=0;i<n;i++) { for(int j=m;j>=d[i];j--) { tag[j]=max(tag[j-d[i]],tag[j]); if(tag[j]) { dp[j]=min(dp[j],dp[j-d[i]]+1); } } } if(dp[m]!=mod) cout<<dp[m]<<endl; else cout<<"><"<<endl;}int main(){ while(cin>>m>>n) { mins=mod; int x, y,j=0,k; for(int i=0;i<n;i++) { cin>>x>>y;//蛋糕的種類(lèi)和美味度 for(k=j;k<j+y;k++)//把蛋糕排列出來(lái) { d[k]=x; } j=k; } // cout<<j<<endl; bfs(j); }}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
