tyvj1340 送礼物


题意简述:

有$n$个物品和一个容量为$w$的背包 求出背包最多能装多大体积的物品
($w\leq 2^{31}-1$,$n\leq 45$)

题解:

该题是经典的超大背包问题 对于这样这样$n$很小$v$很大的背包问题我们可以考虑搜索 假如直接枚举的话那么时间复杂度为$O(2^{45})$显然超时 所以我们可以想到用空间来换时间 也就是折半搜索或者中途相遇法 我们首先把前一半的物品枚举出所有可能的和并放在集合$a$中 时间复杂度$O(2^{\frac{n}{2}})$ 大概是$6\cdot10^6$ 之后我们进行一个排序去重 然后再枚举剩下一半 假如剩下一半和为$sum$ 那么我们从之前的$a$集合中找到$\leq w-sum$的最大的值 这里可以二分操作 把这两个一加就是当前最大的填满的 然后取$max$即可得到$ans$ 总体的时间复杂度大概是$O(2^{\frac{n}{2}}log(2^{\frac{n}{2}}))=O(\frac{n}{2}\cdot 2^{\frac{n}{2}})$

好的 思路看上去也就这样 没啥难的 然后我开心的在acwing交了几发 TLE TLE TLE调过以后在tyvj又交了几发TLE 真是太玄学了 记录一下我的调试历程

首先是若干剪枝 这没啥好说的 在枚举集合时候发现已经超过$w$就退出即可 然后在二分的时候假如当前$sum$加上最小的$a$也大于$w$那么退出

之后是优化搜索顺序 比较套路 我们可以直接考虑排序 让最大的前一半排在前面 这样前面的和就比较大 可以使得后面的搜索树深度减少

然后就是在枚举子集和的时候我一开始是for枚举子集 但是它每一次都会有一个for循环求和的过程 所以还是最好就用dfs去枚举子集和 然后后一半检验是最玄学的 我用for循环枚举子集在tyvj就可以过 用dfs却被卡 然后dfs中的二分改成upper_bound反而又过了 按理来说应该会慢啊 我还试着在acwing上用upper_bound开了O2发现还是比手写慢不少 就很迷惑

另外需要注意的是一半的取值 这里假如直接取$\frac{n}{2}$应该是过不了的反正我过不了 据实验最快的取值应该是$\frac{n}{2}+2$ 我这里来胡扯分析一波

首先我们可以看到瓶颈就是两个dfs 排序本身虽然复杂度也同级但其实不会拖累整体 那么我们第一次dfs时间复杂度是$O(2^{\frac{n}{2}})$ 第二次是$O(\frac{n}{2}\cdot 2^{\frac{n}{2}})$ 其实发现第二次会更大一些 那么我们为了均摊复杂度会想让两次的复杂度差不多 我们考虑一下前一半取$k$个 那么时间复杂度分别为$2^k$和$k\cdot2^{n-k}$ 当$k=\frac{n}{2}+2$时两边分别为$4\cdot2^{\frac{n}{2}}$和$\frac{n+4}{8}\cdot2^{\frac{n}{2}}$

因为$n\in[1,45]$ 所以$n$平均是$23$左右 然后带进去发现前面和4很接近 所以当前一半取$\frac{n}{2}+2$时均摊复杂度是最理想的 当然这个证明有些不严谨 不过应该可以感性理解了

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=(1<<24)+1;
const int N=50;
template<class T>inline void read(T &x) {
    x=0; int ch=getchar(),f=0;
    while(ch<'0'||ch>'9'){if (ch=='-') f=1;ch=getchar();}
    while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    if(f)x=-x;
}
ll a[maxn],w,t,ans;
ll g[N],num;
int n;
void dfs1(int d,ll sum)
{
    if(d==t)
    {
        a[++num]=sum;
        return ;
    }
    dfs1(d+1,sum);
    if(sum+g[d+1]<=w) dfs1(d+1,sum+g[d+1]);
}
void dfs2(int d,ll sum)
{
    if(d==n)
    {
        if(sum+a[1]>w) return ;
        ll temp=w-sum;
        ll l=0,r=num;
        ll t=upper_bound(a+1,a+num+1,temp)-a-1;
        ans=max(ans,a[t]+sum);
        return ;
    }
    dfs2(d+1,sum);
    if(sum+g[t+d+1]<=w) dfs2(d+1,sum+g[t+d+1]);
}
int main()
{
    read(w),read(n);
    for(int i=1;i<=n;i++) read(g[i]);
    sort(g+1,g+n+1);
    reverse(g+1,g+n+1);
    t=n/2+2;
    dfs1(0,0);
    sort(a+1,a+num+1);
    num=unique(a+1,a+num+1)-a-1;
    n-=t;
    dfs2(0,0);
    cout<<ans<<endl;
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
CF1257C Dominated Subarray CF1257C Dominated Subarray
题意简述:给定一个序列 找出其中最短的连续子段使得子段中只有一个众数(子段长度大于等于2) 题解:首先考虑一下假如有一段连续相同的数字 那么答案就一定是2 即从连续的一段中随便挑连续的两个 那么众数就是这个数 那么接下来只剩下没有连续相同
2019-11-14
下一篇 
hdu4388 Stone Game II hdu4388 Stone Game II
1.题意简述:一开始有$n$堆石子和两个人 两个人轮流操作 每次可以一堆有$k$个石子的堆拆分成i和i^k两堆(i<k,i^k<k)每个人在一局中还有一次必杀技可以让i^k变成(2*i)^k假如最后不能操作那么那个人就输 问先手
2019-11-01
  目录