找啊找啊找GF（二维01背包）

解题思路:二维01背包

注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n, m, r, rmb[N], rp[N], t[N];
struct node{
	int cnt, mtime;
}dp[N][N];
int main()
{
	cin >> n;
	for(int i = 0; i < n; ++ i)
		cin >> rmb[i] >> rp[i] >> t[i];
	cin >> m >> r;
	for(int i = 0; i < n; ++ i)
		for(int j = m; j >= rmb[i]; j --)
			for(int k = r; k >= rp[i]; k --){
				int pcnt = dp[k-rp[i]][j-rmb[i]].cnt;
				int ptime = dp[k-rp[i]][j-rmb[i]].mtime;
				if(pcnt + 1 > dp[k][j].cnt ||(pcnt + 1 == dp[k][j].cnt && ptime + t[i] < dp[k][j].mtime))
				{
					dp[k][j].cnt = pcnt + 1;
					dp[k][j].mtime = ptime + t[i];
				}
			}
	int mcnt = 0, mtime= 0;
	for(int j = 0; j <= m; j ++)
		for(int k = 0; k <= r; k ++)
			if(dp[k][j].cnt > mcnt || dp[k][j].cnt == mcnt && dp[k][j].mtime < mtime) {
				mcnt = dp[k][j].cnt;
				mtime = dp[k][j].mtime;
			}
	cout << mtime;
	return 0;
}