题解 P1855 【榨取kkksc03】

· · 题解

题面

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

先分析一下思路：

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

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

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

#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;
}

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

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