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

Question

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

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

Допустим, вот мой вклад:

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-массив. Могут ли некоторые из вас помочь мне с этим и показать слой за слоем, как на моем изображении, как это будет выглядеть? Благодарю.

Answer 1

Допустим, вы используете таблицу с тремя измерениями: A[x][y][z]=k, x: сумма 1-го имущества; y: сумма 2-го свойства; z: сумма 3-го имущества; 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)

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

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

Answer 2

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

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