Алгоритм ранца с дополнительным свойством

Когда есть 1 свойство, я понимаю, что происходит там. У меня проблема с пониманием проблемы с рюкзаком, когда есть более 1 свойства.

enter image description here

Мне нужно написать программу, которая использует алгоритм ранца с двумя свойствами. Учитель сказал нам, что это нужно сделать в 3d-массиве. Я не представляю, как выглядит такой массив.

Скажем здесь мой ввод:

4 3 4 // number of records below, 1st property of backpack, 2nd property  of backpack
1 1 1 // 1st property, 2nd property, cost
1 2 2 // 1st property, 2nd property, cost
2 3 3 // 1st property, 2nd property, cost
3 4 5 // 1st property, 2nd property, cost

И результат будет выглядеть так:

4    // the cheapest sum of costs of 2 records
1 3  // numbers of these 2 records

Объяснение вывода: 2 набора записей вписываются в 1-ю строку ввода:

(1) - номер записи 1 и номер записи 3

  1 1 1
+ 2 3 3
-------
  3 4 4

(2) - номер записи 4

  3 4 5

Поскольку первый набор записей является самым дешевым (4 < 5), мы выбрали его. Не только мне нужно выяснить, существует ли такой набор записей, я также должен найти записи, которые я суммировал.

Но на данный момент мне нужно только понять, как будет выглядеть 3D-массив. Может ли кто-то из вас помочь мне с этим и показать, по-слоям, как и на моем изображении, как это будет выглядеть? Спасибо.

enter image description here

Ответы

Ответ 1

Вы пытаетесь сделать что-то невозможное - это ваша проблема.

Когда вы добавляете число измерений, ваши объекты получают дополнительные свойства. Таким образом, вместо левой стороны столбца таблицы (prop1) у вас есть сторона прямоугольника (prop1 x prop2) или сторона блока (prop1 x prop2 x prop3) и так далее. Но существующие ограничения, определяющие верхнюю часть строки таблицы, должны иметь одинаковое количество измерений. Не только одно измерение!. Таким образом, вы никогда не сможете поставить проблему с двумя свойствами в трехмерный блок, вместо этого вам понадобится блок 4D. 6D блок для 3 свойств и так далее.

Ответ 2

Предположим, вы используете таблицу трех измерений: A[x][y][z]=k, x: сумма 1-го свойства; y: сумма 2-го свойства; z: sum 3rd property; k: минимальная стоимость (максимальное вознаграждение, которое я предпочитаю использовать вознаграждение)

Итак, вы перебираете элементы. Скажем, текущий элемент (p1, p2, p3, вознаграждение) (вознаграждение = - стоимость). для каждой (x,y,z,k), ваша формула обновления:

A[x+p1][y+p2][z+p3] = max(A[x+p1][y+p2][z+p3], A[x+p1][y+p2][z+p3] + reward)

Если первый член на RHS больше, на слоте A[x+p1][y+p2][z+p3], конфигурация рюкзака остается неподвижной; в противном случае вы обновляете рюкзак с помощью A[x+p1][y+p2][z+p3] плюс текущий элемент.

Надеюсь, что это прояснит ситуацию.