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 :-)
It's basically a multidimensional knapsack.
Is it harder to understand than traditional knapsack ? Because I'm also with problems trying to understand the traditional.
:-\
It's exactly the same, but with adding arrays instead of adding numbers.
I think I understood how it can be done. I just need to find a clever way to create this knapsack table. Thanks!