类背包问题

类背包问题

写了个更烂的dfs程序。

#include
#include

int data[40]={0};
int n;
int min=0;

void calculate(int num,int h,int ans)
{
if(num>n+1 | h>19920726) return;//可行性剪枝
if(h==19920726)
{
if(ans>min)
{
min=ans;
}
return;
}
else
{
calculate(num+1,h+data[num],ans+1);
calculate(num+1,h,ans);
}
}

int main(void)
{
int k;
int tmp;
freopen("gift.in","r",stdin);
freopen("gift.out","w",stdout);
scanf("%d",&n);
for(k=1;k<=n;k++)
{
scanf("%d",&tmp);
if(tmp>19920726)
{
n--;
k--;
}
else
{
data[k]=tmp;
}
}
calculate(1,0,0);
printf("%d\n",min);
return 0;
}

我怀疑这题是出自“0726 G4生日练习赛”，我今天刚好在做这个。
我写了个dp的程序，不过我这程序既超时又超内存。
官方的题解是：
Gift的做法：把数组分成前后两半，分别计算前后两半的可取值（不会超时的，O(2^15)），把右边可取值排序（O(log(2^15)*2^15)=O(15*2^15)，再枚举左边的可取值，二分查找就可以了