算法提高贪吃的大嘴

2019-11-11 06:19:01

字体：大中小

来源：转载

供稿：网友

算法提高贪吃的大嘴时间限制：1.0s 内存限制：256.0MB 提交此题问题描述　　有一只特别贪吃的大嘴,她很喜欢吃一种小蛋糕,而每一个小蛋糕有一个美味度,而大嘴是很傲娇的,一定要吃美味度和刚好为m的小蛋糕,而且大嘴还特别懒,她希望通过吃数量最少的小蛋糕达到这个目的.所以她希望你能设计一个程序帮她决定要吃哪些小蛋糕. 输入格式　　先输入一行包含2个整数m、n,表示大嘴需要吃美味度和为m的小蛋糕,而小蛋糕一共有n种,下面输入n行,每行2个整数,第一个表示该种小蛋糕的美味度,第二个表示蛋糕店中该种小蛋糕的总数输出格式　　输出一行包含一个整数表示大嘴最少需要吃的小蛋糕数量,若大嘴无法通过吃小蛋糕达到m的美味度和,则输出”><“. 样例输入 10 2 4 1 2 10 样例输出 4 样例输入 10 2 4 1 7 3 样例输出

< 数据规模和约定　　m ≤ 20000,小蛋糕总数量≤50.

简单背包

搜索直接超时，但是m的数量为2w，n最大为50，所以最多运算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;//蛋糕的种类和美味度 for(k=j;k<j+y;k++)//把蛋糕排列出来 { d[k]=x; } j=k; } // cout<<j<<endl; bfs(j); }}

上一篇：PAT B1037. 在霍格沃茨找零钱（20）

下一篇：欢迎使用CSDN-markdown编辑器