C++14(g++5.4) 解法, 执行用时: 1409ms, 内存消耗: 66040K, 提交时间: 2020-07-20 16:20:43

#include <bits/stdc++.h>

using namespace std;
const int maxn=(1<<24)+10;
int a[50],ret[maxn],upper,cnt1=0,cnt2=0,w;
void dfs(int pos,int cnt)
{
    if(pos>upper) return;
    if((long long)ret[cnt]+a[pos]<=w){
        ret[++cnt2]=ret[cnt]+a[pos];
        dfs(pos+1,cnt2);
    }
    dfs(pos+1,cnt);
}
int main()
{
    int n,ans=0;
    cin>>w>>n;
    for(int i=1;i<=n;i++)  cin>>a[i];
    sort(a+1,a+n+1,greater<int>());
    upper=n/2;dfs(1,0);
    cnt1=cnt2;
    upper=n;dfs(n/2+1,0);
    sort(ret+1,ret+cnt1+1);
    sort(ret+cnt1+1,ret+cnt2+1,greater<int>());
    for(int i=1;i<=cnt1;i++){
    ans=max(ans,ret[i]+*lower_bound(ret+cnt1+1,ret+cnt2+1,w-ret[i],greater<int>()));
    if(ans==w) break;
    }
    cout<<ans;
    return 0;
}

Python3 解法, 执行用时: 3529ms, 内存消耗: 187820K, 提交时间: 2021-08-17 02:28:07

from bisect import bisect_right

W, N = map(int, input().split())
left = set([0])
for i in range(N//2):
    e = int(input())
    for s in list(left):
        tmp = s + e
        if tmp not in left and tmp <= W:
            left.add(tmp)

right = set([0])
for i in range(N - N//2):
    e = int(input())
    for s in list(right):
        tmp = s + e
        if tmp not in right and tmp <= W:
            right.add(tmp)            
right = sorted(right)

ans = 0
for a in left:
    tmp = W - a
    idx = bisect_right(right, tmp) - 1
    if idx >= 0:
        b = right[idx]
        ans = max(ans, a + b)
print(ans)

C++ 解法, 执行用时: 954ms, 内存消耗: 38516K, 提交时间: 2021-10-16 13:56:17

#include<bits/stdc++.h>
using namespace std;
int  n,w,k,cnt=1,ans;
int a[1<<25],g[50];
void dfs1(int v,int sum)
{
	if(v==k)
	{
		a[cnt++]=sum;
		return;
	}
	dfs1(v+1,sum);
	if((long long)sum+g[v]<=w)
	dfs1(v+1,sum+g[v]);
}
void dfs2(int v,int sum)
{
	if(v==n)
	{
		int pos=upper_bound(a,a+cnt,w-sum)-a-1;
		ans=max(ans,a[pos]+sum);
		return; 
	}
	dfs2(v+1,sum);
	if((long long)sum+g[v]<=w)
	dfs2(v+1,sum+g[v]);
}
int main()
{
	cin>>w>>n;
	for(int i=0;i<n;i++)
	cin>>g[i];
	sort(g,g+n,greater<int>());
	k=n/2+2;
	dfs1(0,0);
	sort(a,a+cnt);
	cnt=unique(a,a+cnt)-a;
	dfs2(k,0);
	cout<<ans<<endl;
	return 0;
}