贡献一个背包AC福利

回复帖子 返回题目

@ wuhanru0001 2017-10-12 22:16
#include<stdio.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int sum=0,n,w[10001],f[10001]={0},i,j,r;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
{
    scanf("%d",&w[i]);
    sum+=w[i];
}
    r=sum/2;
    sum=0;
    for(i=1;i<=n;i++)
    for(j=r;j>=w[i];j--)
{
    if(max(f[j],f[j-w[i]]+w[i])<=r)
{
    f[j]=max(f[j],f[j-w[i]]+w[i]);
    sum=max(sum,max(f[j],f[j-w[i]]+w[i]));
}
}
    printf("%d\n",sum);
    return 0;
}