生命不息,奋斗不止

题解 AT1071 【haruki の覚醒め】

2020-11-01 15:57:44


看完题面就知道是背包问题了。

题目分析

题目中$ n $的数据不是特别的强,个人认为用递归的背包是更易懂的。

求选数中大过 $ m $ 的最小的和。然而,我们就可以吧这里的和作为是背包里的物品体积。我们拿题目中样例举例: 过程 包的物品体积不得小于$ 30 $,更新时的条件比起传统的递归就要多增加这么一行语句:

if(sum>=m)

这行代码就是控制背包体积不会小于 $ m $ 。

递归过程

我们在选数过程中用$ dep $来选举数列中的元素。分为两种情况:一种是取当前的,一种是不取当前的,所以就可以用这种代码表示:

dfs(dep+1,sum);
if(sum+a[dep]<=ans)
    dfs(dep+1,sum+a[dep]);

当中的剪枝条件纯粹是为了保证不$ T $的。其实我自己也担心递归的效率由于这道题没有直白的限制容积,所以不需要在这里考虑。 整个递归过程的代码:

void dfs(int dep,int sum)
{
    if(dep>n)
    {
        if(sum>=m)
        {
            if(sum<ans) ans=sum;
        }
    }
    else
    {
        dfs(dep+1,sum);
        if(sum+a[dep]<=ans)
            dfs(dep+1,sum+a[dep]);
    }
}

特殊情况

这道题有一种特殊情况,原题中:请输出最小且大于等于$ m $的,若没有请输出$ -1 $。所以在最后输出时要加一句:

if(ans!=INT_MAX)
    cout<<ans<<endl;
else cout<<-1<<endl;

AC 代码

#include<bits/stdc++.h>
using namespace std;
int a[55],n,m,ans=INT_MAX;
void dfs(int dep,int sum)
{
    if(dep>n)
    {
        if(sum>=m)
        {
            if(sum<ans) ans=sum;
        }
    }
    else
    {
        dfs(dep+1,sum);
        if(sum+a[dep]<=ans)
            dfs(dep+1,sum+a[dep]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dfs(1,0);
    if(ans!=INT_MAX)
        cout<<ans<<endl;
    else cout<<-1<<endl;
    return 0;
}