新手，看大佬思路写的

解题思路:枚举各个瓜

情况有三种：

1. 不买当前瓜

2. 买当前瓜但不劈

3. 买当前瓜劈

由于n<=30,3^30肯定超时间,所以要用折半搜索然后用hash表存前面的贡献，同时劈瓜时可能出现浮点数，可以把瓜重×2，目标值×2，

但要注意当前瓜重和sum很可能会爆int，所以开个long long避免，

注意事项:

1，最好先将瓜重数组降序排序(应该可以理解成可以更早完成m>sum从而return）,不排的话有两个点一直过不去

参考代码:

#include<iostream>

#include<map>

#include<unordered_map>

#include<cmath>

#include<climits>

#include<algorithm>

using namespace std;

int  n,ans=INT_MAX,mid;

long long m;

const int N = 35;

int w[N];

unordered_map<long long, int>h;//用来存前一半的sum和对应最小k值，

void dfs1(int r,long long sum, int k)//分别对应劈瓜次数，此时总重量，此时第几个瓜

{

if (sum > m || k >= ans)return;//当前总重大于目标值或劈瓜数大于已求得最小劈瓜数return（不是最优解）

if (sum == m)

{

ans = min(ans, k);

return;

}

if (r > mid)

{

if (h.count(sum))

{

h[sum] = min(h[sum], k);

}

else

h[sum] = k;

return;

}

dfs1(r+1, sum, k);//不买

dfs1(r+1, sum+w[r], k);//买不劈

dfs1(r + 1, sum + (w[r] >> 1), k + 1);//买劈

}

void dfs2(int r, long long sum, int k)// 跟dfs1基本一样

{

if (sum > m || k >= ans)return;

if (sum == m)

{

ans = min(ans, k);

return;

}

if (h.count(m - sum))

{

ans = min(ans, h[m - sum] + k);

return;

}

if (r > n)

{

return;

}

dfs2(r + 1, sum, k);

dfs2(r + 1, sum + w[r], k);

dfs2(r + 1, sum + (w[r] >> 1), k + 1);

}

int main()

{

cin >> n >> m;

for (int i = 1; i <= n; i++)

{

cin >> w[i];

w[i] <<= 1;//避免浮点数

}

sort(w + 1, w + n,greater<int>());

m <<= 1;

mid = n / 2;

dfs1(1, 0, 0);

dfs2(mid+1, 0, 0);

cout << (ans == INT_MAX ? -1 : ans);

}