M_sea

洛谷1855 榨取kkksc03
Luogu分析二维费用背包裸题,设$f[i][j][k]$表示对于前i个人用j时间和k金钱满足的最多愿望数。对应到...
扫描右侧二维码阅读全文
29
2017/08

洛谷1855 榨取kkksc03

Luogu

分析

二维费用背包裸题,设$f[i][j][k]$表示对于前i个人用j时间和k金钱满足的最多愿望数。
对应到背包问题,压缩一维,则$f[i][j]$表示当前阶段用i时间和j金钱满足的最多愿望数。
那么第i件物品的价值是什么呢?就是1,因为问题问的是最多愿望数。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int f[210][210];
int v[110],s[110]; //第i个物品的金钱、时间 
int main()
{
    int n,Maxv,Maxs,ans=-1;
    scanf("%d%d%d",&n,&Maxv,&Maxs);
    for (int i=1;i<=n;i++) scanf("%d%d",&v[i],&s[i]);
    for (int i=1;i<=n;i++)
        for (int j=Maxv;j>=v[i];j--)
            for (int k=Maxs;k>=s[i];k--)
            {
                f[j][k]=max(f[j][k],f[j-v[i]][k-s[i]]+1);
                ans=max(f[j][k],ans);
            }
    printf("%d\n",ans); 
    return 0;
}

提示

注意到这是二维费用01背包问题,所以要逆推。

最后修改:2019 年 05 月 26 日 02 : 02 PM

发表评论