有三个数组的背包问题：一个物品数组的重量、一个物品数组的值和一个物品数组的数量。

Question

解决这个问题的方法是什么？我认为这将是相当棘手的，因为你必须兼顾三个特征。

这是我的尝试:p值，s重量，k数量，最大最大重量。

m-要带走的物品数量

static int solution(int[] s, int[] p, int[] k, int max) {。

        int[,] matrix = new int[s.Length + 1, max + 1];

        for (int i = 1; i <= s.Length; i++)
        {

            for (int j = 0; j <= max; j++)
            {                    

                int m = 1;
                for(int z = k[i - 1]; z > 0; z--)
                {
                    if(z * s[i - 1] <= j)
                    {                            
                        m = z;
                        break;

                    }
                }                    

                if (s[i - 1] * m <= j)
                {
                    matrix[i, j] =
                        Math.Max((p[i - 1] * m) + matrix[i - 1, j - s[i - 1] * m],
                    matrix[i - 1, j]);
                }
                else
                {
                    matrix[i, j] = matrix[i - 1, j];
                }

            }
        }

        return matrix[s.Length, max];
    }

Answer 1

对于有一定数量的物品副本的背包，有一个很好的技巧可以把它还原成经典的背包。

1. 假设我们有 x 部分项目权重的副本 w 并赋予价值 v

2. 请注意，这与拥有 log x 项目，其中每个项目有 w, 2*w, 4*w...重量和 v, 2*v, 4*v值和所有权重之和等于 w*x

3. 在以下情况下 x 不能用2的幂之和来表示，我们可以把最后一个数字变成剩下的数字（即如果 x=10，我们的权重分布是。1 + 2 + 4 + 3 = 10). 重要的是要选择这样的权重，以使所有可能的选取的 1..x 可以通过选择一些子集来制作

在这之后，问题被简化为经典的knapsack。

复杂度 O(#items * #maxWeight * log2(#MaxItemCount)