题目内容

P1759

在猴王的帮助下,小 A 终于走出了这篇荒山,却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船,但好在小 A 有 n 个潜水工具。由于他还要背重重的背包,所以他只能背 m 重的工具,又因为他的力气并不是无限的,河却很宽,所以他只能背有 v 阻力的工具。但是这条河下有非常重要的数据,所以他希望能够停留的时间最久。于是他找到了你,让你告诉他方案。

大意:0-1 背包,两层限制条件,要求输出方案

解题思路

乍一看,是一个二维的背包问题,还要求输出他的方案,天哪好难,但实际上这题并不难(毕竟是黄题)。思路和榨取 kkksc03 那道题基本类似,唯一不同的是需要记录方案,而且要求字典序尽量的小

回忆:在进行前面的背包问题的时候,是如何判断选与不选的:f[j-w[i]]+c[i] 说明是要选这个物品,而我们现在既然要记录方案,那就只需要在当 f[j-w[i]]+c[i] 更大时记录一下,这个容量下的第 x 个物品被选择了,然后最后输出的时候递推回去就可以了。

这个问题里面,令 g[i][m][v]i 个物品在当前重量为 m,阻力为 v 的时候有没有选,然后最后判断的时候倒序递推,正序输出。

int cnt=0;
    for(int i=n;i>=1;i--)//从最后一个物品开始递推
    {
        if(g[i][m][v])//如果当前状态选了
        {
            ans[cnt++]=i;//记录
            m-=a[i];//回溯上一个状态的 m
            v-=b[i];//回溯上一个状态的 v
        }
    }
    for(int i=cnt-1;i>=0;i--)
        printf("%d ",ans[i]);

还有一点要注意的是需要输出字典序尽可能小的物品,所以在 if(f[j-a[i]][k-b[i]]+c[i]>f[j][k]) (判断选不选物品)的时候必须是大于号,这样才能保证尽量选前面的物品。

#include <cstdio>

int n,m,v,a[105],b[105],c[105],f[205][205];//f 用来进行 dp
bool g[105][205][205];//存储物品的选择
int ans[105];

int main()
{
    scanf("%d %d %d",&m,&v,&n);
    for(int i=1;i<=n;i++)
        scanf("%d %d %d",a+i,b+i,c+i);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i];j--)//常规二维 0-1 背包
            for(int k=v;k>=b[i];k--)
                if(f[j-a[i]][k-b[i]]+c[i]>f[j][k])//注意必须是大于号,否则 WA#2
                    f[j][k]=f[j-a[i]][k-b[i]]+c[i],g[i][j][k]=1;//如果选这个物品可以更优,则进行更新并记录方案
    printf("%d\n",f[m][v]);//先把最优结果输出
    int cnt=0;
    for(int i=n;i>=1;i--)//从最后一个物品开始递推
    {
        if(g[i][m][v])
        {
            ans[cnt++]=i;
            m-=a[i];
            v-=b[i];
        }
    }
    for(int i=cnt-1;i>=0;i--)
        printf("%d ",ans[i]);
    return 0;
}
最后修改日期:2020年2月28日

作者

留言

撰写回覆或留言

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