题目地址：
https://www.acwing.com/problem/content/1379/
学生们在USACO的竞赛中得分越多，我们就越感到高兴。所以我们要尽量将竞赛设计的能够让更多人得到更高的分。为了达到这一目的，请你帮助我们选择一些题目作为比赛用题。共有 N N N种类别的题可以让我们进行选择，同一类别的题做对所花的时间以及得到的分数都是相同的。每种类型的题目出现在一次竞赛中的数量不限，竞赛的时长为 M M M，即所选题目的总耗时不得超过 M M M，但可以小于 M M M。请问，我们如何安排各种类型的题目在竞赛中出现的数量，能够使得用户的得分最多。竞赛中不一定要出现所有类型的题目。输出用户可能的最高得分。
输入格式：
第一行包含两个整数
M
,
N
M,N
M,N，分别表示竞赛时长以及题目种类数量。接下来
N
N
N行，每行包含两个整数
p
,
t
p,t
p,t，分别表示一种类型题目的分数以及耗时。
输出格式：
输出一个整数，表示用户可能得到的最大分数。
数据范围：
1
≤
M
,
N
,
p
,
t
≤
1
0
4
1≤M,N,p,t≤10^4
1≤M,N,p,t≤104
其实可以看成是个完全背包问题，可以用动态规划来做。代码如下：
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010;
int n, m;
int w[N], v[N];
int f[N];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++)
// 完全背包里体积从小到大更新
for (int j = w[i]; j <= m; j++)
f[j] = max(f[j], f[j - w[i]] + v[i]);
cout << f[m] << endl;
return 0;
}
时间复杂度 O ( N M ) O(NM) O(NM)，空间 O ( M ) O(M) O(M)。
