题目链接： P5194 [USACO05DEC]Scales S
解题思路： 虽然题目中说n≤1000 ，但考虑到“每个砝码的质量至少等于前面两个砝码的质量的和”这一条件，可以推出 n≤30 。所以可以用搜索。可以考虑折半搜索。把40个砝码分成两半，搜索出两边分别能测量的重量，然后枚举其中一边的所有可以测量到的重量，将另外一边排序后二分，使得相加不超过C且尽量大。在所有答案中取min即可。
代码：
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 5000000;
bool vis[maxn];
long long n,n1, c, a[maxn],sum[maxn],maxweight,cnt1,cnt2,xa[maxn],xb[maxn];
inline void DFS1(int L, int R,long long sum) {
if (sum > c) {
//超过最大重量，返回return;}if (L > R) {
//到达最右端，记录答案xa[++cnt1] = sum;return;}DFS1(L+1, R, sum);//取DFS1(L+1, R, sum + a[L]);//不取
}
inline void DFS2(int L, int R, long long sum) {
if (sum > c) {
return;}if (L > R) {
xb[++cnt2] = sum;return;}DFS2(L+1, R, sum);DFS2(L+1, R, sum + a[L]);
}
int main() {
cin >> n1 >> c;for (int i = 1; i <= n1; i++) {
int x;cin >> x;if (x < c) {
//一个砝码的重量大于最大重量，不记录数组a[++n] = x;}}DFS1(1, n / 2, 0);DFS2(n / 2 + 1, n, 0);sort(xb + 1, xb + 1 + cnt2);//将xb数组排序for (int i = 1; i <= cnt1; i++) {
int index = upper_bound(xb + 1, xb + 1 + cnt2, c - xa[i]) - xb;//upper_bound找到第一个严格大于c-xa[i]的数字位置index//也就是说xa[i]+xb[index]严格大于m//那么这个位置前面一个就一定小于等于c-xa[i]//于是就有xa[i]+xb[index-1]<=cmaxweight = max(maxweight, xa[i] + xb[index - 1]);}cout << maxweight << endl;
}