題目大意：
有n（1~30）天，第i天花費vi（1~10^8），總錢數m（0~10^8）。
每天可以選擇花費或不花費。
問最多能花多少錢。
題目思路：
題意和01背包差不多，不過01背包會爆掉O(nm),復雜度太高了，而且數組也開不下。
因為n只有30，所以試著用深搜+剪枝。
設當前的累加花費為tot，當前為第i天，mmin[i]表示i~n中的最小值，sum[i]表示a[i]+...+a[n]，ret表示當前最優值。
剪枝一：tot>m,顯然後面都不需要訪問了。
剪枝二：tot+sum[i]<=ret,顯然後面不會出現比當前最優值更優的了。
剪枝三：tot+mmin[i]>m,顯然後面的值無論怎麼加是不合法的。
剪枝四：tot+sum[i]<=m,顯然後面訪問後可達的最優值為tot+sum[i]了。（這個做題的時候沒發現）
剪枝五：ret==m,顯然不可能出現更優的了，也不需要訪問了。
我是用了剪枝（1，2，3，5）才過了，不過不知道為什麼有的人用（1，2，5）就過了，而且0ms。。
代碼也沒發現比較奇特的地方。。
代碼：
[cpp]
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll __int64
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define eps (1e-8)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#pragma comment(linker, "/STACK:102400000,102400000")
template <class T> T _max(T x,T y){return x>y? x:y;}
template <class T> T _min(T x,T y){return x<y? x:y;}
template <class T> T _abs(T x){return (x < 0)? -x:x;}
template <class T> T _mod(T x,T y){return (x > 0)? x%y:((x%y)+y)%y;}
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
template <class T> void getmax(T& x,T y){x=(y > x)? y:x;}
template <class T> void getmin(T& x,T y){x=(x<0 || y<x)? y:x;}
int TS,cas=1;
const int M=100000+5;
int n,m,a[33],sum[33],mmin[33],ret;
void dfs(int p,int tot){
if(tot>m || ret==m) return;
ret=_max(ret,tot);
if(p>n || tot+sum[p]<=ret || tot+mmin[p]>m) return;
dfs(p+1,tot+a[p]);
dfs(p+1,tot);
}
void run(){
int i,j;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
ret=0;
for(i=1,j=m;i<=n && j;i++)
if(ret+a[i]<=m) ret+=a[i];
sum[n]=mmin[n]=a[n];
for(i=n-1;i>=1;i--) sum[i]=sum[i+1]+a[i];
for(i=n-1;i>=1;i--) mmin[i]=_min(mmin[i+1],a[i]);
dfs(1,0);
printf("%d\n",ret);
}
void preSof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while((~scanf("%d%d",&n,&m))) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll __int64
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define eps (1e-8)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define PI (acos(-1.0))
#pragma comment(linker, "/STACK:102400000,102400000")
template <class T> T _max(T x,T y){return x>y? x:y;}
template <class T> T _min(T x,T y){return x<y? x:y;}
template <class T> T _abs(T x){return (x < 0)? -x:x;}
template <class T> T _mod(T x,T y){return (x > 0)? x%y:((x%y)+y)%y;}
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
template <class T> void getmax(T& x,T y){x=(y > x)? y:x;}
template <class T> void getmin(T& x,T y){x=(x<0 || y<x)? y:x;}
int TS,cas=1;
const int M=100000+5;
int n,m,a[33],sum[33],mmin[33],ret;
void dfs(int p,int tot){
if(tot>m || ret==m) return;
ret=_max(ret,tot);
if(p>n || tot+sum[p]<=ret || tot+mmin[p]>m) return;
dfs(p+1,tot+a[p]);
dfs(p+1,tot);
}
void run(){
int i,j;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
ret=0;
for(i=1,j=m;i<=n && j;i++)
if(ret+a[i]<=m) ret+=a[i];
sum[n]=mmin[n]=a[n];
for(i=n-1;i>=1;i--) sum[i]=sum[i+1]+a[i];
for(i=n-1;i>=1;i--) mmin[i]=_min(mmin[i+1],a[i]);
dfs(1,0);
printf("%d\n",ret);
}
void preSof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while((~scanf("%d%d",&n,&m))) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}
