打表计算前K个物体任意组合的重量

步骤为：
1. dfs(u,s) u为第u个物品，s为当前重量
2. 若u==k 说明已经枚举到第k个物品，存入当前重量s
3. 分两种情况，选第u个物品和不选第u个物品，选第u个物品时要注意判断u+w<=m

cnt=unique(weight,weight+cnt)-weight;
返回weight数组中不重复的元素的个数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;

const int N=46;
int w[N];
int weight[1<<25];
int cnt=1;
int ans;
int n,m;
int k;

void dfs1(int u,int s)
{
    if(u==k)
    {
        weight[cnt++]=s;
        return;
    }
    //不选第u个物品
    dfs1(u+1,s);
    //选第u个物品
    if((ll)w[u]+s<=m) dfs1(u+1,s+w[u]);
}

void dfs2(int u,int s)
{
    if(u==n)
    {
        int l=0,r=cnt-1;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(weight[mid]<=m-s) l=mid;
            else r=mid-1;
        }
        ans=max(ans,weight[l]+s);
        return;
    }
    dfs2(u+1,s);
    if((ll)s+w[u]<=m) dfs2(u+1,s+w[u]);
}

int main()
{
    cin>>m>>n;
    for(int i=0;i<n;i++) cin>>w[i];
    sort(w,w+n);
    reverse(w,w+n);

    k=n/2+2;
    dfs1(0,0);
    sort(weight,weight+cnt);

    cnt=unique(weight,weight+cnt)-weight;


    dfs2(k,0);
    cout<<ans;
    return 0;
}