[洛谷]榨取kkksc03

题面

给你一定的时间和背包容量,现在有$n$个物品,选择它们,需要一定的时间还需耗费你的一定背包容量。求最多能选几个物品。

先分析一下思路:

如果只有一件费用,那么就可以直接上贪心了。将费用$sort$一遍,然后就直接一样一样的选。

可是现在是二维的费用了,也就是说它有两项费用需均衡同时考虑。这就是一道明显的二维费用的背包问题了。

首先我们枚举物品用一层循环枚举容量,然后再用一层循环枚举时间;我们就考虑一下,我们是选当前这件物品,还是不选。如果选我们还剩多少的背包容量和时间,然后它的总收益就是剩下的能选的最大数$+1$,在和当前已知的用同样的时间和背包容量能选的最大值比较,取最大值,就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
int n,m,t,m1[105],t1[105],f[205][205];
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>t;
for(int i = 1; i <= n; ++ i)
cin>>m1[i]>>t1[i];
for(int i = 1; i <= n; ++ i)
for(int j = m; j >= m1[i]; -- j)
for(int k = t; k >= t1[i]; -- k)
f[j][k] = max(f[j][k],f[j - m1[i]][k - t1[i]]+1);
cout<<f[m][t];
return 0;
}

附加:如果你实在不会打动态规划,那么你也可以用记忆化搜索,这两种方法本质都是一样的)

不过建议你还是学习一下动态规划吧,毕竟动规只是思路比较难,但动规实现还是很好的。