先把所有体重加起来再除以2，然后作为总重量用01背包DP一边，得到最大价值的剩余空间乘2然后输出，应该没问题啊

#include<iostream>

using namespace std;

int main()

{ int t=0,n,w[101],dp[101];

memset(dp,0,sizeof(dp));

cin>>n; for(int i=1;i<=n;i++){cin>>w[i];t+=w[i];}

t/=2;

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

for(int j=t;j>=w[i];j--)

dp[j]=max(dp[j],dp[j-w[i]]+w[i]);

t=2*(t-dp[t]);

cout<<t<<endl;

return 0;}

回复 楼主892611452 的帖子

我和你的思路代码都几乎一样啊，也是没有输出。

#include<stdio.h>

#define max(a,b) (a>b?a:b)

#define maxn 101

int main()

{

int man[maxn],dp[maxn]={0};

int n,i,j,ans=0,h=0;

scanf("%d",&n);

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

{

scanf("%d",&man[i]);

h+=man[i];

}

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

{

for(j=h/2;j>=man[i];j--)

{

dp[j]=max(dp[j],dp[j-man[i]]+man[i]);

ans=max(dp[j],ans);

}

}

printf("%d\n",h-2*ans);

return 0;

}

我把数组开大就AC了

#include<cstdio>

#define max(a,b) (a>b?a:b)

using namespace std;

int main()

{

int man[101],dp[10001]={0}; //看其他的评论，后面的数组开成10001就可以了，但我不知道原因

int n,i,j,ans=0,h=0;

scanf("%d",&n);

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

{

scanf("%d",&man[i]);

h+=man[i];

}

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

{

for(j=h/2;j>=man[i];j--)

{

dp[j]=max(dp[j],dp[j-man[i]]+man[i]);

ans=max(dp[j],ans);

}

}

printf("%d\n",h-2*ans);

return 0;

}

我把数组开大就AC了

#include<cstdio>

#define max(a,b) (a>b?a:b)

using namespace std;

int main()

{

int man[101],dp[10001]={0}; //看其他的评论，后面的数组开成10001就可以了，但我不知道原因

int n,i,j,ans=0,h=0;

scanf("%d",&n);

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

{

scanf("%d",&man[i]);

h+=man[i];

}

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

{

for(j=h/2;j>=man[i];j--)

{

dp[j]=max(dp[j],dp[j-man[i]]+man[i]);

ans=max(dp[j],ans);

}

}

printf("%d\n",h-2*ans);

return 0;

}

看题就知道为啥要开大数组了

一个人最大100KG，最多100个人，自然开到10001是最好的

#include"stdio.h"

main()

{

int i,j;

int n,v[300];

int s=0,V;

int a[20000];

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d",&v[i]);

s+=v[i];

}

V=s/2;

for(i=0;i<n;i++)

for(j=V;j>=v[i];j--)

a[j]>?=a[j-v[i]]+v[i];

printf("%d",s-2*a[V]);

}

开20000也是可以

楼主数组开小了

n虽<=100，但是楼主既然用背包解此题，如若测试数据如下：

5

99 99 99 99 99

该当若何？

99*5=495，自然超过了101，当然会无输出。

注意数据范围