如何在3d数组中实现背包算法，具有两个属性，每个属性必需的权重和最小总值？

Question

卡车问题：

我们至少需要物品1的W1重量和物品2的W2重量，以获得最小的燃气总价值。 每辆卡车运载物品1的w1重量，物品2的w2重量和花费v气体。

例如，输入将是：

5 60 5    // W1, W2, number of records below
3 36 120  // w1, w2, v
10 25 129 // w1, w2, v
5 50 250  // w1, w2, v
1 45 130  // w1, w2, v
4 20 119  // w1, w2, v

输出应该是：

249

我需要实现一个功能

int truck_knapsack(int W1, int W2, int w1[], int w2[], int v[], int n);

它返回燃气消耗的最小总值，其中

• n是记录数（卡车），
• 燃气消耗的v[]值，
• 第1项的w1[]权重，
• qazxsw poi iterm2的重量，
• w2[] item1的必要重量，
• qazxsw poi必需的iterm2重量。

我发现了类似的问题陈述和解决方案，但我无法为此找到解决方案。

我的老师指示我用3d数组自下而上的方法解决这个问题，但任何解决方案都会非常有用。

Answer 1

我相信你可以使用W1描述的策略。你的问题不是一个直接的背包配方，但它可以被改造成一个。

设置TotalW1 =Σw1i-W1和TotalW2 =Σw2i-W2。现在你可以解决一个W2

• 最大化Σxivi
• 约束1：Σxjw1j≤TotalW1 - W1
• 约束2：Σxjw2j≤TotalW2 - W2

为了获得针对您的问题的最小化问题陈述的解决方案，您只需采用背包解决方案的补充，即未选择的卡车是在承载预期的最小总重量时最小化燃气消耗的卡车。 根据问题，输出应该是满足重量条件的卡车的总价值。下面是一个递归算法，显示了您的问题示例：

this answer

输出是249。