在对数组应用给定操作后最大化数组的总和

Question

给定一个由N个元素组成的数组A和一个整数K。你可以对数组执行以下操作任意次数（可以是0次）。

从数组A中选择一个元素，记为A[i]
选择一个正整数Y。
将 A[i] 改为 A[i] xor Y。

操作中使用的所有 Y 的总和不应大于 K。

你的任务是求出数组A所有元素运算后的最大和

示例：-

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

输出：- 36

解释：- 在第一个操作中，选择第四个元素并且Y=2。然后把4改成4 xor 2，就是6。更新后的数组将是：- 9,7,7,6,3

第二个操作，选择第五个元素，Y=4。然后把3改成3 xor 4，就是7。更新后的数组将为 9,7,7,6,7 因此总和为 36.

请有人解释问题背后的逻辑。我不明白。

Answer 1

由于您没有澄清我对 Y 的评论，我假设答案是否定的，您不能将唯一 Y 值计入预算 K。

这个问题简直就是变相修改0-1knapsack problem。使用背包问题解决它：

将物品价值和重量对定义为集合

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

应用动态规划解决0-1背包问题，重量限制K，以及每个a \in A只能提取一件物品的要求。背包问题的总最优权重+任意未修改的a \in A就是解

这里是 python 中的一个实现，它解决了给定的例子。

#!/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))

在对数组应用给定操作后最大化数组的总和

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

arrays

algorithm

bit

xor