个人备案网站建设方案书,wordpress评论vip,西安市建设工程信息网诚信信息平台官网,开发微网站和小程序题干#xff1a;
问题描述 有一只特别贪吃的大嘴,她很喜欢吃一种小蛋糕,而每一个小蛋糕有一个美味度,而大嘴是很傲娇的,一定要吃美味度和刚好为m的小蛋糕,而且大嘴还特别懒,她希望通过吃数量最少的小蛋糕达到这个目的.所以她希望你能设计一个程序帮她决定要吃哪些小蛋糕.
输…题干
问题描述 有一只特别贪吃的大嘴,她很喜欢吃一种小蛋糕,而每一个小蛋糕有一个美味度,而大嘴是很傲娇的,一定要吃美味度和刚好为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. 解题报告 转化成0-1背包求解就行了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX 2e5 5;
const int INF 0x3f3f3f3f;
int tot;
int v[105];
int dp[20005];
int main()
{int n,m;cinmn;for(int val,num,i 1; in; i) {scanf(%d%d,val,num);for(int j 1; jnum; j) {v[tot] val;}}memset(dp,INF,sizeof dp);dp[0] 0;for(int i 1; itot; i) {for(int j m; jv[i]; j--) {dp[j] min(dp[j],dp[j-v[i]]1);}}if(dp[m] ! INF) printf(%d\n,dp[m]);else puts();return 0 ;}
