Score Inflation
The more points students score in our contests, the happier we here at the USACO are. We try to design our contests so that people can score as many points as possible, and would like your assistance.
We have several categories from which problems can be chosen, where a "category" is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the USACO staff how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest.
The input includes the length of the contest, M (1 <= M <= 10,000) (don’t worry, you won’t have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 <= N <= 10,000.
Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is worth (1 <= points <= 10000); the second tells the number of minutes a problem from that category takes to solve (1 <= minutes <= 10000).
Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points.
PROGRAM NAME: inflate
INPUT FORMAT
Line 1: M, N — contest minutes and number of problem classes
Lines 2-N+1: Two integers: the points and minutes for each class
SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20
OUTPUT FORMAT
A single line with the maximum number of points possible given the constraints.
SAMPLE OUTPUT (file inflate.out)
605
描述
学生在我们USACO的竞赛中的得分越多我们越高兴。
我们试着设计我们的竞赛以便人们能尽可能的多得分,这需要你的帮助。
我们可以从几个种类中选取竞赛的题目,这里的一个"种类"是指一个竞赛题目的集合,解决集合中的题目需要相同多的时间并且能得到相同的分数。你的任务是写一个程序来告诉USACO的职员,应该从每一个种类中选取多少题目,使得解决题目的总耗时在竞赛规定的时间里并且总分最大。输入包括竞赛的时间,M(1 <= M <= 10,000)(不要担心,你要到了训练营中才会有长时间的比赛)和N,"种类"的数目1 <= N <= 10,000。后面的每一行将包括两个整数来描述一个"种类":
第一个整数说明解决这种题目能得的分数(1 <= points <= 10000),第二整数说明解决这种题目所需的时间(1 <= minutes <= 10000)。你的程序应该确定我们应该从每个"种类"中选多少道题目使得能在竞赛的时间中得到最大的分数。
来自任意的"种类"的题目数目可能任何非负数(0或更多)。
计算可能得到的最大分数。
格式
PROGRAM NAME: inflate
INPUT FORMAT：
(file inflate.in)
第 1 行: M, N–竞赛的时间和题目"种类"的数目。
第 2-N+1 行: 两个整数:每个"种类"题目的分数和耗时。
OUTPUT FORMAT：
(file inflate.out)
单独的一行包括那个在给定的限制里可能得到的最大的分数。
SAMPLE INPUT
300 4
100 60
250 120
120 100
35 20
SAMPLE OUTPUT
605
======================== 华丽的分割线 ========================
标准的无限背包,, 看<<背包9讲>>
/*
LANG: C
ID: zqy11001
PROG: inflate
*/
#include <stdio.h>
#define getint(i) scanf(%d, &i)
#define max(a, b) ((a)>(b)?(a):(b))
int f[10001];
int main(void)
{
int n, m;
int i, j, t;
int a, b;
freopen(inflate.in, r, stdin);
freopen(inflate.out, w, stdout);
getint(m);
getint(n);
for(i = 1; i <= n; i++){
scanf(%d%d, &a, &b);
for(j = b; j <= 10000; j++){
t = f[j - b] + a;
f[j] = max(f[j], t);
}
}
printf(%d\\n, f[m]);
return 0;
}