苹果+zb的生日+邮票分你一半（DP01背包）

今天终于走进了传说中的动态规划，哈哈，虽然只是一个皮毛，但一样很开心，下面三个题，苹果是最基本的01背包问题，然后是邮票问题，最后是zb的生日，呵呵，今天一下子搞了三道，希望明天能够再接再厉！！

题目：苹果

原题地址：请猛击

#include<stdio.h>
#include<string.h>
int bag[1004];
void dp(int v,int c,int w)
{
for(int i=v;i>0;i--)
{
if(i>=c && (w+bag[i-c])>bag[i])
bag[i]=w+bag[i-c];
}
}
int main()
{
int n,v,i,j,c,w;
while(scanf("%d%d",&n,&v),n+v)
{
memset(bag,0,sizeof(bag));
for(i=1;i<=n;i++)
{
scanf("%d%d",&c,&w);
dp(v,c,w);
}
printf("%d\n",bag[v]);
}
return 0;
}        

题目：邮票分你一半

原题地址：请猛击

#include<stdio.h>
#include<string.h>
int stamp[10005],money[100000];
void dp(int sum,int num)
{
int k=sum/2;
for(int i=1;i<=num;i++)
{
for(int j=k;j>0;j--)
{
if(stamp[i]+money[j-stamp[i]]>money[j]&&j>=stamp[i])
money[j]=stamp[i]+money[j-stamp[i]];
}
}
printf("%d\n",sum-money[k]*2);
}
int main()
{
int n,a;
scanf("%d",&a);
while(a--)
{
memset(stamp,0,sizeof(stamp));
memset(money,0,sizeof(money));
int sum=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&stamp[i]);
sum+=stamp[i];
}
dp(sum,n);
}
return 0;
}        

题目：zb的生日

原题地址：请猛击

#include<stdio.h>
#include<string.h>
#define max(a,b) (a)>(b)?a:b 
int xigua[25],weight[100010];
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int sum=0;
memset(xigua,0,sizeof(xigua));
memset(weight,0,sizeof(weight));
for(int i=1;i<=n;i++)
{
scanf("%d",&xigua[i]);
sum+=xigua[i];
}
int k=sum/2;
for(int i=1;i<=n;i++)
{
for(int j=k;j>0;j--)
if(j>=xigua[i]) weight[j]=max(weight[j],xigua[i]+weight[j-xigua[i]]);
}
printf("%d\n",sum-weight[k]*2);
}
return 0;
}        

代码不写思路，只说明是给自己看的，呵呵，你懂得，因为这并不是传说中的模板！！！