How to divide a set of values ​​into two sets of a fixed size so that their sums approach a certain value

Question

I have a set of 18 values ​​(it will always be 18), which I need to distribute into two sets, one of 10 elements and one of 8 elements.

The distribution rule is that the values ​​of each set should be equal (or as close as possible) to a certain known value - therefore, in the first set, the sum of the values ​​should be as close as possible to 1500000 and in the second set of the sum iof the values ​​should be as close as possible to 1,000,000.

What is the best (and this may mean the simplest) algorithm for this?

For further clarification, values ​​range from 110,000 to 200,000. Values ​​are always a multiple of 100 and are positive integer targets, and there may be duplicates.

Answer 1

There are only 43,758 such elections. Go through each of them and find the best.

Answer 2

This is an optimization problem. Here you have two optimization criteria that should be combined into one. For example, for example:

F(A, B) = w1*abs(sum(A) - 1500000) + w2*abs(sum(B) - 1000000)

where A and B are your sets, sum () is the sum of the elements in the set, and w1 and w2 are the weights.

Then you should find a strategy to iterate over possible combinations. The simplest strategy is to find all 10 combinations of 18 and choose the one that minimizes F (A, B). There are C (18.10) = 43758 combinations.

Answer 3

, , , , , - . , , ( ) .

(, 100), 1100 2000, "" 10 1100, 1200 . 50/1100, 5%. , , .

, , () () 18.

p.s SUBSET SUM ( KNAPSACK ) NP-. .

Answer 4

, , np, .

- 18 10 8 . .

Answer 5

. , ( ) , .