Imagine that we have n numbers. Given a certain number k . We need to display the numbers, which together will give the closest possible number to k from all possible combinations.

For example: 4 numbers are given: 8, 6, 3, 1 . Given the number k: k=13 . The answer will be: 8, 3, 1 , because 8 + 3 + 1 = 12 is the maximum number of possible combinations close to 13 .

PS: there are no limitations. This is not an olympiad challenge, just for a project at school. 1<n<50 . 1<k<1000 .

If possible, please write the program in pascal, but you can also in C ++. I need to understand the algorithm.

  • one
    Standard "backpack problem". - Akina
  • The answer will be: 8 3 1, because 8 + 3 + 1 = 12 - this is as close as possible to 13 number of possible combinations Why not 8 + 6 = 14? also differs by just one ... - Akina
  • But after all, in the backpack problem, two parameters are used: weight and cost. And here I see only one parameter. And in the knapsack problem, we try to take the maximum cost, the main thing is that the weight does not exceed the maximum. What can I take for the second parameter? - Rafael Sayfutdinov
  • 8 and 6 can also be taken, but at least I should decide this way - Rafael Saifutdinov
  • Two parameters are used in the backpack problem: weight and cost. You have a degenerate task. All costs are equal. 8 and 6 can also be taken. But this is a mess - the selection algorithm must be unambiguous. Enter additional criteria. For example, give priority to a larger or smaller amount with equal deviations. - Akina

1 answer 1

Get an array of length K + 1 A:array[0..K] of Integer , fill with zeros, A[0] := -1

For each C[i] value, scan the array from the end. The value of P can be compiled from cc=С[i] and the pre-typed sum pс = P - С[i] , if the corresponding cell A[pc] nonzero. In this case, write the value cc in A[P]

After you need to check the array from the end. If the K-th or previous cells are non-zero - you can type the corresponding amount and, having passed to the beginning, you can find out its components.

  • What is the value of P? Array c is what I understand is an array with given numbers, right? - Rafael Sayfutdinov
  • The cell of the array A [p] corresponds to the sum of p. C [] - yes, an array with the given numbers - MBo