题干：

https://www.luogu.org/problemnew/show/U43391

自01背包问世之后，小A对此深感兴趣。一天，小A去远游，却发现他的背包不同于01背包。 小A的背包最多能装W的价值
现有n件物品，分别为v1,v2,v3……vn
问如何存放物品，使背包内物品总价值达到最大

输入输出格式

输入格式：

 

输入第一行包含两个整数，分别代表n和W。 以后N行，每行一个正整数vi 表示第i个物品的价值 ​

 

输出格式：

 

输出仅一个整数，即最大价值。

 

输入输出样例

输入样例#1： 

5 10
1
3
4
8
9

输出样例#1： 

10

说明

1 <= n <= 40
1 <= vi <= 1e7
1 <= w <= 1e9

解题报告：

   这题显然是背包问题，但是就是没法用背包做。直接暴力加点剪枝就可以过了，而且跑的很快，毕竟数据水、、并且题目说了是暴力AC。

   但是正解是什么呢？很玄学、、把n从中间分成两份，然后答案就是三种情况：要么都在第一份，要么都在第二份，要么在第一份和第二份中各一个。很类似那道【CodeForces - 799C】Fountains  的做法。这里给出syt学长的代码。

暴力代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[55];
int n,m,loc;
ll ans = 0;

void dfs(int x,ll cur) {
	if(x == loc) {
		ans = max(ans,cur);
		return;
	}
	ans = max(ans,cur);
    for(int i = x+1; i<=loc; i++) {
		if(cur+a[i] <= m)
    		dfs(i,cur+a[i]);
    }
}
int main()
{
    cin>>n>>m;
    for(int i = 1; i<=n; i++) scanf("%lld",a+i);
    sort(a+1,a+n+1);
    for(int i = 1; i<=n; i++) {
        loc = i;
        if(a[i] > m) break;
    }
    dfs(1,0);
    if(a[1] <= m)
        dfs(1,a[1]);
    printf("%lld\n",ans);
    return 0 ;
 }

其中dfs函数也可以这么写：

void dfs(int x,ll cur) {//代表截止当前(x)位置，价值为cur的状态。 
    ans = max(ans,cur);
	if(x == loc) return;
    for(int i = x+1; i<=loc; i++) {
        if(cur+a[i] <= m) dfs(i,cur+a[i]);
    }
}

或者这样：

void dfs(int x,ll cur) {
    if(x == loc) {
		ans = max(ans,cur);
		return;
    }
	if(cur+a[x+1] <= m)
		dfs(x+1,cur+a[x+1]);
	dfs(x+1,cur);
}

其实这些代码都是等价的，画一个搜索树就看出来了。但是刚开始写也会写崩、、反正还是没理清楚到底表示的是什么状态。 

AC代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e6+10;

ll a[maxn],b[maxn];
ll v[50];
ll w;
int pre[50];
int n;

void init() {
	int i;
	pre[0]=1;
	for(i=1; i<=30; i++) pre[i]=2ll*pre[i-1];//2的n次方 
}

int main() {
	ll t,sum,ans;
	int i,j,k,l,r,m,p;
	init();
	scanf("%d%lld",&n,&w);
	for(i=1; i<=n; i++) scanf("%lld",&v[i]);

	ans=0;
	for(i=0; i<pre[n/2]; i++) {
		t=i,sum=0,j=n/2,k=1;
		while(j>0) {
			if(t%2) sum+=v[k];
			t/=2,j--,k++;
		}
		a[i]=sum;
		if(sum<=w) ans=max(ans,sum);
	}
	for(i=0; i<pre[n-n/2]; i++) {
		t=i,sum=0,j=n-n/2,k=n/2+1;
		while(j>0) {
			if(t%2) sum+=v[k];
			t/=2,j--,k++;
		}
		b[i]=sum;
		if(sum<=w) ans=max(ans,sum);
	}

	sort(b,b+pre[n-n/2]);
	/*
	printf("*%d %d*\n",pre[n/2],pre[n-n/2]);
	for(i=0;i<pre[n/2];i++) printf("%lld ",a[i]);
	printf("\n");
	for(i=0;i<pre[n-n/2];i++) printf("%lld ",b[i]);
	printf("\n");
	*/
	
	for(i=0; i<pre[n/2]; i++) {
		if(a[i]<w) {
			l=0,r=pre[n-n/2]-1,p=-1;
			m=(l+r+1)/2;
			while(l<r) {
				m=(l+r+1)/2;
				if(a[i]+b[m]<=w) l=m;
				else r=m-1;
			}
//			printf("l = %d\n",l);
			if(l!=0) ans=max(ans,a[i]+b[l]);
		}
	}
//		for(i=0; i<pre[n/2]; i++) {
//		if(a[i]<w) {
//			l=0,r=pre[n-n/2]-1,p=-1;
//			while(l<=r) {
//				m=(l+r)/2;
//				if(a[i]+b[m]<=w) l=m+1,p=m;
//				else r=m-1;
//			}
//			printf("p = %d\n",p);
//			if(p!=-1) ans=max(ans,a[i]+b[p]);
//		}
//	}
	printf("%lld\n",ans);
	return 0;
}

骚操作：

#include<bits/stdc++.h>
#define Mit map<int,bool>::iterator
using namespace std;
typedef long long ll;
map<int,bool> M;
vector<int> V;
int main()
{
    int n,w;
    scanf("%d%d",&n,&w);
    int x;
    for(int i=0;i<n;i++){
        scanf("%d",&x);
        V.clear();
        if(x<=w){
            V.push_back(x);
            for(Mit it=M.begin();it!=M.end()&&it->first<=w-x;it++){
                V.push_back(it->first+x);
            }
            for(int j=0;j<V.size();j++){
                M[V[j]]=true;
            }
        }
    }
    ll ans=0;
    Mit it=M.upper_bound(w);
    if(it!=M.begin()){
        it--;
        ans=it->first;
    }
    printf("%d\n",ans);
    return 0;
}