前端之家收集整理的这篇文章主要介绍了
NYOJ 325 zb的生日 【dp问题】，
前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。
这是一个可以用动态规划解决的题，可以看成是01背包的变形吧。。尽管出题人原意可能是让我们用搜索做的，但由于时间卡的不紧，于是我们可以水过。。。。本人用dp以2996ms水过（题目时间限制是3000ms）。。ac后看看本题排名就悲剧了，倒数第一。。⊙﹏⊙。。
不扯废话了，看代码吧。。
#include<stdio.h>
#include<algorithm>
int main()
{
int a,b,n,m,v;
while(scanf("%d",&v)!=EOF)
{
int yi[100001]={0};
int ok[10000];
int sum=0,sum1;
for(a=1;a<=v;a++)
{
scanf("%d",&ok[a]);
sum+=ok[a];
}
sum1=sum/2;
for(b=1;b<=v;b++)
{
for(m=sum1;m>=ok[b];m--)
{
if(yi[m]<(yi[m-ok[b]]+ok[b]))
yi[m]=yi[m-ok[b]]+ok[b];
}
}
printf("%d\n",sum-2*yi[sum1]);
}
}
原文链接：https://www.f2er.com/vb/260286.html
