Блог пользователя abdalimran

Problem: Searching N elements from an array which sum is X
Автор abdalimran, 10 лет назад, По-английски

You are given S,X and N.

S = size of an array

N = number of elements you have to find

X = sum

You have to find N elements from the array which sum is X.

Input:

7 25 3

1 5 10 7 13 15

Output:

5 7 13

If there are multiple solution you can output any of them. What are the best possible solutions with least complexity for this problem?

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The best complexity may depend on the constraints. What are they?

→ Ответить
»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It is NP-complete (if we let X be 0 and then enumerate all possible N, we solve subset sum problem).

Nevertheless, you can do pseudo polynomial knapsack-like solution. Denote array A and its elements as A1, ..., An. Let OPT(x, i, n) be equal true if we can get sum x choosing n elements from {A1, ..., Ai} (the first i elements of A) and false otherwise. We can recalculate it as following:

→ Ответить