1036: 分配宝藏
时间限制: 1 Sec 内存限制: 128 MB
提交: 331 解决: 108
[提交][状态][讨论版]
题目描述
两个寻宝者找到一个宝藏，里面包含着n件物品，每件物品的价值是w[i]。suma代表寻宝者A所获物品的总价值，sumb代表寻宝者B所获物品的总价值，请问怎么分配，能使得|suma - sumb|（即suma与sumb之差的绝对值）最小。
输入
有多组输入数据，第一行为一个数字T，代表有T组输入数据 (0
//这是高复杂度的
#include<stdio.h>
#include<math.h>
#define max(a,b) (a>b)? a : b
int a,b,c,k,n,hn;
int main()
{int i,j;scanf("%d",&k);while(k--){scanf("%d",&n);int w[n+1];int v[n/2][n/2];for(i=1;i<=n;i++)scanf("%d",&w[i]);int sum=0;int hsum;for(i=1;i<=n;i++){sum+=w[i];}hsum=(sum+1)/2;hn=(n+1)/2;for(i=0;i<=n;i++){v[i][0]=0;}for(i=0;i<=hsum;i++){v[0][i]=0;}for(i=1;i<=n;i++){for(j=1;j<=hsum;j++){v[i][j]=v[i-1][j];if(w[i]<=j)v[i][j]=max(v[i][j],v[i-1][j-w[i]]+w[i]);}}a=v[n][hsum];b=sum-a;c=abs(b-a);printf("%d\n",c);
}return 0;} //这是优化过后的
#include<stdio.h>
#include<math.h>
#include<string.h>
#define max(a,b) (a>b)? a : b
int a,b,c,k,n,hn;
int v[20001];
int w[201];
int main()
{int i,j;scanf("%d",&k);while(k--){memset(v,0,sizeof(v));memset(w,0,sizeof(w));int sum=0;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&w[i]);sum+=w[i];} int hsum;hsum=(sum+1)/2;hn=(n+1)/2;for(i=1;i<=n;i++){for(j=hsum;j>=w[i];j--){v[j]=max(v[j],v[j-w[i]]+w[i]);}}