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

Автор Sazzon, история, 8 лет назад, По-английски

Hi!

An interesting problem appeared at work today. I've managed to reduce the problem into what seems to be a solvable problem. Here it is:

Given an resultant array A of C elements and a list of N arrays, also with C elements. Is there a way to sum a subset of the N given arrays such that every element in the i-th position is summed with the element on the i-th position of the other array and result in the given array A? Let me give you an example:

C = 3

N = 6

A = {2,1,1}

N arrays:

1 = {1,0,1} 2 = {1,1,0} 3 = {1,0,1} 4 = {1,0,0} 5 = {0,1,1} 6 = {0,1,0}

The best answer is both 1 and 2 or 2 and 3. If we sum 1,0,1 + 1,1,0 = 2,1,1 or 1,1,0 + 1,0,1 = 2,1,1.

Have you ever came across a problem like this ? Is there any problem here in codeforces which has the same solution or editorial ? Do you know any technique that maybe useful for this purpose. If you have any input, please feel more than welcome to share.

Thank you in advance :-)

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

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

It's basically a multidimensional knapsack.

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

    Is it harder to understand than traditional knapsack ? Because I'm also with problems trying to understand the traditional.

    :-\

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

      It's exactly the same, but with adding arrays instead of adding numbers.

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

        I think I understood how it can be done. I just need to find a clever way to create this knapsack table. Thanks!