题干：

问题描述

　　有一只特别贪吃的大嘴,她很喜欢吃一种小蛋糕,而每一个小蛋糕有一个美味度,而大嘴是很傲娇的,一定要吃美味度和刚好为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代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#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;
	cin>>m>>n;
	for(int val,num,i = 1; i<=n; i++) {
		scanf("%d%d",&val,&num);
		for(int j = 1; j<=num; j++) {
			v[++tot] = val;
		}
	}
	memset(dp,INF,sizeof dp);
	dp[0] = 0;
	for(int i = 1; i<=tot; i++) {
		for(int j = m; j>=v[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 ;
 }