題目描述

約翰有一架用來稱牛的體重的天平。與之配套的是 N (1≤N≤1000) 個已知質量的砝碼（所有砝碼質量的數值都在 32 位帶符號整數范圍內）。

每次稱牛時，他都把某頭奶牛安置在天平的某一邊，然后往天平另一邊加砝碼，直到天平平衡，于是此時砝碼的總質量就是牛的質量（約翰不能把砝碼放到奶牛的那邊，因為奶牛不喜歡稱體重，每當約翰把砝碼放到她的蹄子底下，她就會嘗試把砝碼踢到約翰臉上）。

天平能承受的物體的質量不是無限的，當天平某一邊物體的質量大于 C (1≤C≤2
30
) 時，天平就會被損壞。砝碼按照它們質量的大小被排成一行。并且，這一行中從第 3 個砝碼開始，每個砝碼的質量至少等于前面兩個砝碼（也就是質量比它小的砝碼中質量最大的兩個）的質量的和。

約翰想知道，用他所擁有的這些砝碼以及這架天平，能稱出的質量最大是多少。由于天平的最大承重能力為 C，他不能把所有砝碼都放到天平上。

現在約翰告訴你每個砝碼的質量，以及天平能承受的最大質量，你的任務是選出一些砝碼，使它們的質量和在不壓壞天平的前提下是所有組合中最大的。

輸入格式

第 1 行輸入兩個用空格隔開的正整數 N 和 C。

第 2 到 N+1 行：每一行僅包含一個正整數，即某個砝碼的質量。保證這些砝碼的質量是一個不下降序列。

輸出格式

輸出一個正整數，表示用所給的砝碼能稱出的不壓壞天平的最大質量。

題目分析

此題用經典的dfs搜索，剪枝函數和回溯函數是核心，由于給出的砝碼按從小到大排列，則顯然從后往前搜索更方便
dfs(cur,i)其中cur為當前計算值，i為從i到0檢索
剪枝函數：創建砝碼的前綴和數組b[i]，當cur+b[i]<max時，停止檢索，因為往后搜索max不會再變（max為答案）
回溯函數：當cur>C時（主要），轉而從i-1處檢索，即dfs(cur,i-1)

代碼實現

#include<bits/stdc++.h>
using namespace std;
long long a[100],b[100];
int N,C,maxx=0;

void dfs(int cur,int index){
    if(cur+b[index]<maxx) return;
    maxx=maxx>cur?maxx:cur;
    if(index==0) return;
    if(cur+a[index]<=C){
        dfs(cur+a[index],index-1);
    }
    dfs(cur,index-1);
}


int main(){
    cin>>N>>C;
    int i=1;
    b[0]=0;
    while(i<=N){
        cin>>a[i];
        if(a[i]>C) break;
        b[i]=b[i-1]+a[i];
        i++;
    }
    dfs(0,i-1);
    cout<<maxx;
    return 0;
}