思路:DP,01背包
------------
这道题目可以说是一道裸的 01背包,唯一的不同仅仅只是将原来的一维改成了两维。我不明白为什么是一道 普及/提高- 的题,所以在评分时评了普及-。
对于每一个愿望,只有两种选择:要么满足,要么不满足。然后 01背包跑一遍就 AC 了。
$ \rm code $
# include <bits/stdc++.h> using namespace std; # define maxM 205 int n, m, t, dp[maxM][maxM]; //定义 dp 数组 int main() { cin >> n >> m >> t; for(int i = 1, x, y; i <= n; ++i) { //为了方便,省去了两个数组,直接边读边做 cin >> x >> y; for(int j = m; j >= x; --j) for(int k = t; k >= y; --k) //注意!里层和中层的两个循环必须是倒序的,否则就变成了完全背包! dp[j][k] = max(dp[j][k], dp[j - x][k - y] + 1); //要么不满足,要么满足 } cout << dp[m][t] << endl; //最后输出最大值即可 return 0; }