题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1673
题意：
有n个砝码(n <= 1000)，重量为w[i]。
你要从中选择一些砝码，使得这些砝码的总重量最大，但不超过c。
w[i]按递增顺序给出，并且保证w[i] >= w[i-1]+w[i-2] (i >= 3)。
题解：
dfs。
因为w[i] >= w[i-1]+w[i-2]，所以其实n最大只有45左右（类似斐波那契数列）。
优化：
（1）启发式：优先选砝码（不跳过），并且优先选重量大的砝码，尽早更新ans。
（2）A*搜索：如果当前tot + 剩下砝码的总重（前缀和） < ans，则return。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 1005 using namespace std; int n,c;
int ans=;
int w[MAX_N];
long long sum[MAX_N]; void dfs(int col,int tot)
{
if(tot>c) return;
ans=max(ans,tot);
if(col>n) return;
if(tot+sum[n]-sum[col-]<=ans) return;
dfs(col+,tot+w[col]);
dfs(col+,tot);
} void read()
{
cin>>n>>c;
for(int i=n;i>=;i--)
{
cin>>w[i];
}
} void solve()
{
sum[]=;
for(int i=;i<=n;i++)
{
sum[i]=sum[i-]+w[i];
}
dfs(,);
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}