M_sea

洛谷1855 榨取kkksc03
前言很明显这是广告233题目描述(广告部分省略)洛谷的运营组决定,如果一名oier向他的教练推荐洛谷,并能够成功的...
扫描右侧二维码阅读全文
29
2017/08

洛谷1855 榨取kkksc03

前言

很明显这是广告233

题目描述

(广告部分省略)
洛谷的运营组决定,如果一名oier向他的教练推荐洛谷,并能够成功的使用,那么他可以浪费掉kkksc03的一些时间的同时消耗掉kkksc03的一些金钱以满足自己的一个愿望。

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

算法

二维费用背包裸题,设fi[k]表示对于前i个人用j时间和k金钱满足的最多愿望数。
对应到背包问题,压缩一维,则fi表示当前阶段用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++) //核心DP部分  
        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背包问题,所以要逆推。

最后修改:2018 年 11 月 09 日 03 : 52 PM

发表评论