自动搬运

查看原文

来自洛谷，原作者为

	StudyingFather 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。

搬运于2025-08-24 22:08:06，当前版本为作者最后更新于2019-01-16 23:37:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

乍一看，感觉和装箱问题一样，但是仔细看一下数据范围，就知道背包的做法是不可行的。

虽然题目中说 $n \leq 1000$ ，但考虑到“每个砝码的质量至少等于前面两个砝码的质量的和”这一条件，可以推出 $n \leq 30$ 。

在这么小的数据范围下，我们考虑用搜索的方法来解决这道题。

#include <iostream>
#include <algorithm>
using namespace std;
long long sum[1005],a[1005],ans,n,c;
void dfs(int cur,long long x)
{
 if(x>c)return;
 if(sum[cur-1]+x<=c)
 //一个剪枝：如果前面那些砝码可以全部取走，那直接取走即可。
 {
  ans=max(ans,sum[cur-1]+x);
  return;
 }
 ans=max(ans,x);
 for(int i=1;i<cur;i++)
  dfs(i,x+a[i]);
 return;
}
int main()
{
 cin>>n>>c;
 for(int i=1;i<=n;i++)
 {
  cin>>a[i];
  sum[i]=sum[i-1]+a[i];
 }
 dfs(n+1,0);
 cout<<ans<<endl;
 return 0;
}