洛谷P1855-榨取kkksc03（二维01背包）

题目描述：

洛谷的运营组决定，如果一名 OIer 向他的教练推荐洛谷，并能够成功的使用（成功使用的定义是：该团队有 202020 个或以上的成员，上传 101010 道以上的私有题目，布置过一次作业并成功举办过一次公开比赛），那么他可以浪费掉 kkksc03 的一些时间的同时消耗掉 kkksc03 的一些金钱以满足自己的一个愿望。

kkksc03 的时间和金钱是有限的，所以他很难满足所有同学的愿望。所以他想知道在自己的能力范围内，最多可以完成多少同学的愿望？

输入格式：

第一行三个整数 n,M,T，表示一共有 n（1≤n≤100）个愿望， kkksc03 的手上还剩 M（0≤M≤2000）元，他的暑假有 T（0≤T≤200）分钟时间。

第 2~n+1 行 mi, ti 表示第 i 个愿望所需要的金钱和时间。

输出格式：

一行，一个数，表示 kkksc03 最多可以实现愿望的个数。

输入输出样例：

输入 #1复制

6 10 10
1 1
2 3 
3 2
2 5
5 2
4 3

输出 #1复制

4

AC Code：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1001
int dp[N][N],money[N],times[N];
int n,m,t;
int main() {
	cin>>n>>m>>t;
	for(int i=1;i<=n;i++) {
		cin>>money[i]>>times[i];//每个愿望所需的金钱和时间 
	}
	for(int i=1;i<=n;i++) {//一共n个愿望 
		for(int j=m;j>=money[i];j--) {//金钱 
			for(int k=t;k>=times[i];k--) {//时间
				/*每个愿望要么实现，要么不实现（即01背包问题）
				有金钱和时间两个限制条件，所以是二维01背包问题
				一维减去该愿望所需金钱，二维减去该愿望所需时间，实现愿望个数+1*/ 
				dp[j][k]=max(dp[j][k],dp[j-money[i]][k-times[i]]+1);
			}
		}
	}
	cout<<dp[m][t]<<endl;
	return 0;
}

本文地址：https://blog.csdn.net/weixin_43823808/article/details/107589815