AcWing 171. 送礼物
原题链接
简单
作者:
lqmm1
,
2021-12-05 22:49:51
,
所有人可见
,
阅读 335
/*
背包问题当我们n*m不大的时候我们就是用经典的dp做法
当m很大n中等的时候一般会根据某种性质贪心来完成
如果m很大但n很小的时候我们可以用dfs爆搜来枚举方案数来完成
爆搜有一种很棒的空间换时间的方式我们可以先爆搜预先处理出来一部分做成一个表
然后爆搜其他部分然后通过查表的方式完成整体的爆搜
这题我们可以预处理出前面的放法能产生的值然后我们搜后面的每次在前面找能组合的小于m的最大值是多少整体取最大
查表的时候我们可以提前把表排序然后二分来查这样就会快不少
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
#define int long long
using namespace std;
int dp[1<<25],ans;
int ai[50];
int m,n;
int cnt;
bool cmp(int a,int b)
{
return a>b;
}
void dfs(int u,int k,int sum)
{
if(u>k)
{
dp[++cnt]=sum;
return;
}
dfs(u+1,k,sum);
if(sum+ai[u]<=m)dfs(u+1,k,sum+ai[u]);
}
void dfs1(int u,int sum)
{
if(u>n)
{
int l=1,r=cnt;
while(l<r)
{
int mid=l+r+1>>1;
if(dp[mid]+sum<=m)l=mid;
else r=mid-1;
}
ans=max(ans,dp[l]+sum);
return;
}
dfs1(u+1,sum);
if(sum+ai[u]<=m)dfs1(u+1,sum+ai[u]);
}
signed main()
{
cin >> m>>n;
for(int i=1;i<=n;i++)
cin >> ai[i];
sort(ai+1,ai+1+n,cmp);
int k=n/2+2;
dfs(1,k,0);
sort(dp+1,dp+cnt+1);
dfs1(k+1,0);
cout << ans<<endl;
return 0;
}