题目内容

P1855

大意:有 n 个需要时间为 t_i,金钱为 m_i 的愿望,一共有 M 元钱,T 时间,求最多能完成多少愿望

解题思路

这还是一个背包问题,只不过维度增加了一维,开到了二维,但总体的 0-1 背包思路是不变的。

f(n,i,j) 表示放入前 n 个物品,金钱容量为 i,时间容量为 j 的“背包”最多能装下的愿望个数,即最多能满足的愿望个数,然后枚举即可。

f(n,i,j)=\max(f(n,i,j),f(n-1,i-m_i,j-t_i)+1)

同样的,数组的第一维可以滚动掉

代码细节:

  • 因为我很蠢,所以一开始 f 数组的容量没有开够,是需要以最大时间和最大空间来开的,而不是已物品数量(RE了两回)
  • 转移方程部分代码较长,容易打错(错了一次)

代码:

#include <cstdio>

int n,M,T,m[105],t[105];
int f[205][205];

inline int max(int _a,int _b)
{
    return _a>_b?_a:_b;
}

int main()
{
    scanf("%d %d %d",&n,&M,&T);
    for(int i=1;i<=n;i++)
        scanf("%d %d",m+i,t+i);
    for(int i=1;i<=n;i++)
        for(int j=M;j>=m[i];j--)//倒序枚举
            for(int k=T;k>=t[i];k--)//倒序枚举
                f[j][k]=max(f[j][k],f[j-m[i]][k-t[i]]+1);
    printf("%d\n",f[M][T]);
    return 0;
}
最后修改日期:2020年3月1日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。