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

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

1 голос
/ 31 марта 2019

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

Нам нужно как минимум 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-матрица снизу вверх», но любое решение было бы очень полезным.

1 Ответ

0 голосов
/ 02 апреля 2019

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

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

  • развернуть ∑x i v i
  • ограничение 1: ∑x j w 1j ≤ TotalW 1 - W 1
  • ограничение 2: ∑x j w 2j ≤ TotalW 2 - W 2

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

#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.

...