current position:Home>174 allocation treasure binary violence solution error

174 allocation treasure binary violence solution error

2022-02-02 22:13:30 CSDN Q & A

Problem description
Two treasure hunters found a treasure , It contains n Item , The value of each item is W[0],W[1],…W[n-1].
SumA On behalf of treasure hunters A The total value of the goods obtained ,SumB On behalf of treasure hunters B The total value of the goods obtained , I would like to ask you how to distribute the goods so that the total value difference between the two people is the smallest , That is, the absolute value of the difference between the total value of the goods obtained by two people |SumA - SumB| Minimum .

Enter description
The input data consists of two lines :
The first line is a positive integer n, Indicates the number of items , among 0<n<=200.
The second line has n A positive integer , They represent the value of each item W[i], among 0<W[i]<=200.

The output shows that
For each set of data , Output an integer |SumA-SumB|, The minimum value of the difference between the sum of the values of two people's goods .

sample input
4
1 2 3 4

sample output
0

#include<stdio.h>#include<math.h>int min=200,w[200],op[200],n;int main(){    scanf("%d",&n);    for(int i=0;i<n;++i)    scanf("%d",&w[i]);    int b=pow(2,n);    for(int i=0;i<b;++i)    {        int result=0;        for(int j=0;j<n;++j)        {            op[j]=i>>j&1;            if(op[j])            result-=w[j];            else            result+=w[j];        }        if(result>=0)        min=result<min?result:min;    }    printf("%d",min);    return 0;} 

The sample did not time out




Refer to the answer 1:
#include<stdio.h>#include<string.h>#include<math.h>#include<stdlib.h> const int N=1e6+10;const int INF=0x3f3f3f3f;const int MOD=2008;int max(int a,int b){    return a>=b?a:b;}int a[110], dp[1000010];int main (){        int T, n, i, j, sum, suma, sumb, ans;         sum = 0;         scanf("%d", &n);        for (i = 1; i <= n; i++)        {            scanf("%d", &a[i]);            sum += a[i];        }         memset(dp, 0, sizeof(dp));         for (i = 1; i <= n; i++)        {            for (j = sum/2; j >= a[i]; j--)            {                dp[j] = max(dp[j], dp[j-a[i]]+a[i]);// One dimensional simplified version             }        }         suma = dp[sum/2];        sumb = sum-suma;         ans = abs(suma-sumb);         printf("%d\n", ans);         return 0;}



Refer to the answer 2:

copyright notice
author[CSDN Q & A],Please bring the original link to reprint, thank you.
https://en.primo.wiki/2022/02/202202022213290407.html

Random recommended