题目描述 有一只特别贪吃的大嘴,她很喜欢吃一种小蛋糕,而每一个小蛋糕有一个美味度,而大嘴是很傲娇的,一定要吃美味度和刚好为m的小蛋糕,而且大嘴还特别懒,她希望通过吃数量最少的小蛋糕达到这个目的.所以她希望你能设计一个程序帮她决定要吃哪些小蛋糕.
数据规模和约定 m ≤ 20000,小蛋糕总数量≤50.
输入 先输入一行包含2个整数m、n,表示大嘴需要吃美味度和为m的小蛋糕,而小蛋糕一共有n种,下面输入n行,每行2个整数,第一个表示该种小蛋糕的美味度,第二个表示蛋糕店中该种小蛋糕的总数 输出 输出一行包含一个整数表示大嘴最少需要吃的小蛋糕数量,若大嘴无法通过吃小蛋糕达到m的美味度和,则输出" > < “. 样例输入 10 2 4 1 2 10 样例输出 4
#include<cstring> #include<iostream> #include<algorithm> #define inf 0xfffffff using namespace std; int val[55],num[55]; int dp[55][20001]; int main() { int m,n; cin >> m >> n; for(int i=0;i<n;i++) cin >> val[i] >> num[i]; int s=0; fill(dp[0],dp[0]+55*20001,inf); //memset(dp,inf,sizeof(dp));//一开始写的memset 调了半天不对 memset主要用来给字符串赋值 //赋int值时要注意的问题很多，还是老实用fill完事了 dp[0][0]=0; int cnt=1;//给所有蛋糕编号 for(int i=0;i<n;i++) { for(int j=1;j<=num[i];j++) { for(int k=0;k<=m;k++) { if(k>=val[i]&&dp[cnt-1][k-val[i]]!=inf&&dp[cnt][k]>dp[cnt-1][k-val[i]]+1) dp[cnt][k]=dp[cnt-1][k-val[i]]+1; } for(int k=0;k<=m;k++) dp[cnt][k]=min(dp[cnt-1][k],dp[cnt][k]); cnt++; } } if(dp[cnt-1][m]!=inf) cout << dp[cnt-1][m]; else cout << "><"; }