算法提高 贪吃的大嘴 时间限制：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.
这道题的模型是一道经典的问题：最少硬币问题，而最少硬币问题就是背包问题，所以采用dp解决。
给两个最少硬币问题的参考链接，一个是用一维做的，一个是用二维：
http://blog.csdn.net/jiyanfeng1/article/details/39315643
http://www.cppblog.com/jince/archive/2010/09/17/126857.aspx
#include <iostream> #define INF 0x3fffffff using namespace std; int t[51]; int coin[51]; int dp[20002] = {0}; int main(){ //freopen( "123.txt", "r", stdin ); int n; int m; int i, j, k; cin >> m >> n; //int *t = new int[n+1]; //int *coin = new int[n+1]; for( i = 1; i<= n; i++ ) { cin >> t[i] >> coin[i]; } for( i = 1; i <= m; i++ ) { dp[i] = INF; } dp[0] = 0; for( i = 1; i <= n; i++ ) for( j = 1; j <= coin[i]; j++ ) for( k = m; k >= t[i]; k-- ) { dp[k] = min( dp[k - t[i]] + 1, dp[k] ); } if( dp[m] == INF ) cout << "><" << endl; else cout << dp[m] << endl; return 0; }
