I have a question about the java combination.

Asked 2 years ago, Updated 2 years ago, 21 views

You want to input n (even number) and n coins, divide into two teams, and print the minimum number of coins for two teams. If you enter 6 and 10 20 30 40 30 20, the value should be output as 10.

I thought we should divide the teams first, so I printed it out in combination.

'''

public static void main(String[] args) {
    // // TODO Auto-generated method stub

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();

    int[] s = new int[n];
    int[] bucket = new int[n/2];

    for(int i = 0; i < s.length; i++)
        s[i] = sc.nextInt();

   pick(s, n, bucket, n/2, n/2);
}
public static void pick(int[] item, int itemSize, int[] bucket, int bucketSize, int k)
{// combination

    int i, total = 0, sum = 0;
    int smallest, lastIndex, min = 999999;

    for(i = 0; i < itemSize; i++) {
        total += item[i];
    }

    if ( k == 0 ) // trivial case
    {
        int team = 0;
        for(i = 0; i < bucketSize; i++) {
            System.out.printf("%s ", item[bucket[i]]);
            sum += item[bucket[i]];
        }
        System.out.println(sum);
        return;
    }
    lastIndex = bucketSize - k - 1;

    if(bucketSize == k)
        smallest = 0;
    else
        smallest = bucket[lastIndex]+1;

    for(i = smallest; i < itemSize; i++)
    {
        bucket[lastIndex+1] = i;
        pick( item, itemSize, bucket, bucketSize, k-1 );
    }
}'''

Implementing this code will output the number of n/2 coins and n/2 coin agreements.

In order to output the minimum number of coins for both teams, one of them must be selected, but it was blocked.

If you get the total of the item value and subtract the sum, the sum of the coins of the other team comes out, so I thought you could find the difference between sum and the coins of the other team, put them in the array except for the overlapping values, and return them. But it's very difficult to implement.

I'm not sure whether the logic I thought was wrong or not.

I would appreciate it if you could implement the code. Even if you suggest a direction, I'll think about it a little more and solve it again. Thank you.

java c

2022-09-21 16:27

1 Answers

I think we need a mathematical solution for this, but the following is just a vague idea, so please verify it.

If it's like this, I think it's possible to calculate it based on the middle value.

Since I'm a liberal arts major, this glue may be wrong, so I think you can check it yourself and correct the deficiencies or mistakes before coding them. The idea that comes to mind now is, "There must be a term or topic that calls for this kind of problem," but I'm not sure about that.


2022-09-21 16:27

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.