arrays - Maximize sum of array after applying the given operations on the array

Question

Given an Array A consisting of N elements and an integer K. You can perform following operations on array any number of times(Can be 0).

1. Choose an element from array A. Let us denote as A[i]

2. Choose a positive integer Y.

3. Change A[i] to A[i] xor Y.

The Sum of all the Y's used in the operations should not be greater than K.

Your task is to find the maximum sum of all the elements of array A after operations.

Example:-

N=5
K=6
A={9,7,7,4,3}

Output:- 36

Explanation:- In the first operation, choose the fourth element and Y=2. Then change 4 to 4 xor 2, that is 6. the updated array will be:- 9,7,7,6,3

In second Operation, choose the fifth element and Y=4. Then change 3 to 3 xor 4, that is 7. The updated array will be 9,7,7,6,7 Hence sum is 36.

Please someone explain the logic behind the problem. I am not getting the idea.

标签： arraysalgorithmbitxor

Answer 1

Since you didn't clarify my comment about Y I will assume that the answer is no, you can not count unique Y values once towards the budget K.

This problem is simply a modified 0-1 knapsack problem in disguise. To solve it using the knapsack problem:

Let the item value & weight pairs be defined as the set

I = { (Y ^ a - a, Y) : a \in A, Y \in {1,K}}

Apply the dynamic programming solution to the 0-1 knapsack problem with weight limit K, and the requirement that only one item may be picked per a \in A. The total optimal weight of the knapsack problem + any unmodified a \in A is the solution.

Here is an implementation in python that solves the example given.

#!/usr/bin/python

def solve2(w,v,W,nK):
    n = len(w)
    m = dict()

    for j in range(0,W+1):
        m[-1, j] = 0
    for i in range(-1,n):
        m[i, 0] = 0

    for i in range(0,n):
        for j in range(0,W+1):
            b_w = -1
            b_v = -1
            found = False
            for k in range(0,nK):
                if w[i][k] <= j and v[i][k] >= b_v:
                    b_w = w[i][k]
                    b_v = v[i][k]
                    found = True
            if found:
                m[i, j] = max(m[i-1, j], m[i-1, j-b_w] + b_v)
            else:
                m[i, j] = m[i-1, j]
    return m[n-1,W]


A = [9,7,7,4,3]
K = 6
v = [ [ (Y^a)-a for Y in range(1,K+1) ] for a in A]
w = [ [ Y for Y in range(1,K+1) ] for a in A]
print ('Solution value is:', sum(A) + solve2(w,v,K,K))