Как реализовать алгоритм ранца в трехмерном массиве с двумя свойствами, необходимыми весами для каждого и минимальным суммарным значением?

Question

Проблема с грузовиком:

Нам нужно как минимум W1 вес предмета 1 и W2 вес предмета 2 для минимального общего значения расходуемого газа.
Каждый грузовик несет w1 весиз item1, w2 вес item2 и расходует 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[] значения израсходованного газа,
• w1[] веса элемента 1,
• w2[] веса элемента 2,
• W1 необходимый весof item1,
• W2 необходимый вес item2.

Я нашел похожие формулировки проблемы и решения, но мне не удалось найти решение для этого.

Мой учитель дал мне указание решить эту проблему с использованием подхода «3d-матрица снизу вверх», но любое решение было бы очень полезным.

Answer 1

Я считаю, что вы могли бы использовать стратегию, описанную этим ответом .Ваша проблема не является прямой формулировкой ранца, но она может быть преобразована в одну.

Set TotalW ₁ = ∑w _1i - W ₁ и TotalW ₂ = ∑w _2i - W ₂ .Теперь вы можете решить задачу Рюкзак с множественными ограничениями

• развернуть ∑x _i v _i
• ограничение 1: ∑x _j w _1j ≤ TotalW ₁ - W ₁
• ограничение 2: ∑x _j w _2j ≤ TotalW ₂ - W ₂

Чтобы получить решение для постановки задачи минимизациина ваш вопрос вы просто берете дополнение к рюкзачному решению, то есть не выбранные грузовики - это те, которые минимизируют потребление газа при минимальной ожидаемой общей массе.
В соответствии с вопросом, результатом должна быть общая стоимостьгрузовых автомобилей, которые соответствуют условиям веса.Ниже приведен рекурсивный алгоритм, показывающий пример вашего вопроса:

#include <stdio.h>

int max(int a, int b)
{
  return (a > b ? a : b);
}

int truck_knapsack(int W1, int W2, int w1[], int w2[], int v[], int n)
{
  if (n == 0 || W1 == 0 || W2 == 0)
    return 0;

  if (w1[n - 1] > W1 || w2[n - 1] > W2)
    return truck_knapsack(W1, W2, w1, w2, v, n - 1);

  return max(
      v[n - 1] + truck_knapsack(W1 - w1[n - 1], W2 - w2[n - 1], w1, w2, v, n - 1),
      truck_knapsack(W1, W2, w1, w2, v, n - 1));
}

int main()
{
  int W1 = 5;
  int W2 = 60;
  int w1[] = {3, 10, 5, 4, 1};
  int w2[] = {36, 25, 50, 45, 20};
  int v[] = {120, 129, 250, 130, 119};
  int n = 5;

  // the problem statement is a variation of Knapsack problem
  // turn it into a classical Knapsack problem

  // total1 = sum of w1 weights - W1
  int total1 = 0;
  for (int i = 0; i < n; i++)
    total1 += w1[i];
  total1 -= W1;

  // total2 = sum of w2 weights - W2
  int total2 = 0;
  for (int i = 0; i < n; i++)
    total2 += w2[i];
  total2 -= W2;

  // the result of the Knapsack algorithm is the max
  // bounded by total1 and total2
  // the result of the original problem statement is sum_of_values - result
  int result = truck_knapsack(total1, total2, w1, w2, v, n);
  int sum_values = 0;
  for (int i = 0; i < n; i++)
    sum_values += v[i];
  printf("%d\n", sum_values - result);

  return 0;
}

Вывод 249.