原题连接

题目描述

达达帮翰翰给女生送礼物，翰翰一共准备了N个礼物，其中第i个礼物的重量是G[i]。

达达的力气很大，他一次可以搬动重量之和不超过W的任意多个物品。

达达希望一次搬掉尽量重的一些物品，请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式
第一行两个整数，分别代表W和N。

以后N行，每行一个正整数表示G[i]。

输出格式
仅一个整数，表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围
$1≤N≤45$
$1≤W,G[i]≤2^31−1$

样例

输入样例：
20 5
7
5
4
18
1
输出样例：
19

双向搜索+剪枝

首先这道题目肯定是要搜索的,因为如果说用DP做的话,那么这个W值太大了,但是如果说只是普通搜索的话,那么O(2^N)的复杂度足以超时,而且这道题目重点就是,我们已经知道了初态而且还知道了终态,既然如此的话,我们可以选择双向搜索.

根据双向搜索的性质,我们大致可以确定当前搜索的范围,首先从前一半个物品中,挑选任意多个物品,然后将这些物品的权值总和加入到数组S中,然后我们就会发现在这个S数组中有很多很多的重复的数值,既然如此,我们不妨将他们统统都删掉,至于如何删掉,相信STL中的unique可以满足你的需求.然后我们现在前半部分搜索完后,开始搜索后半部分,至于后半部分搜索,其实和前半部分一模一样,只是我们需要二分找到当前可以填写的最大值.

现在我们已经确定好了搜索后,我们就需要剪枝了.

优化搜索顺序:我们可以将物品从大到小排序,然后再开始搜索

选择适当的折半搜索点:根据LYD大佬亲身随机试验,我们发现如果第1~n/2+2个物品为前一半的时候,我们的时间是最快的不要问我为什么,因为实验和数据告诉我们真相

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=(1<<24)+1;
long long ans,n,m,a[N],s[N],n_2;
long long find(int val)//二分查找
{
    int l=1,r=n_2,check=m-val;//最大可以承受的值
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if (s[mid]<=check)
            l=mid;
        else
            r=mid-1;
    }
    ans=max(ans,s[l]+val);//当前最大值与全局最大值开始比较
}
int cmp(long long a,long long b)
{
    return a>b;
}
int dfs(int x,long long sum)
{
    if (x==(n/2+2)+1)
    {
        s[++n_2]=sum;//新的权值出现,压入数组中
        return true;//返回必不可少,否则RE
    }
    dfs(x+1,sum);//不放这个进去
    if (sum+a[x]<=m)//可以放进去
        dfs(x+1,sum+a[x]);
}
int dfs2(int x,int sum)
{
//  cout<<x<<endl;
    if (x==n+1)
    {
        find(sum);//求出当前可以填充的最大值
        return true;
    }   
    dfs2(x+1,sum);
    if (sum+a[x]<=m)//如果可以放进去
        dfs2(x+1,sum+a[x]);
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>m>>n;
    for(int i=1; i<=n; i++)
        cin>>a[i];
    sort(a+1,a+1+n,cmp);//从大到小排序
    dfs(1,0);
    sort(s+1,s+n_2+1);
    n_2=unique(s+1,s+n_2+1)-(s+1);//去掉重复后,多少个数
    dfs2(n/2+3,0);
    cout<<ans<<endl;
    return 0;
}