Выберите продукты, чтобы получить максимальную стоимость корзины

Question

Учитывая список продуктов, доступных в магазине, мне нужно выбрать набор продуктов для моей тележки таким образом, чтобы мое значение корзины было максимально возможным. Ограничения, как, тележка имеет размер l*w*h. Выбранные продукты должны индивидуально и полностью вставляться в корзину, что дает максимальную возможную ценность для тележки. Можно выбрать один элемент на продукт.

У меня есть product id, price, l, w, ht, weight каждого продукта со мной. Как это можно сделать?

Я придумал логику, как показано ниже.

1. объем Рассчитать повозки
2. Рассчитать объем продукта и стоимость продукта на кубический сантиметр, используя его цене
3. Сортировки списка продукта на основе стоимости/CUCM
4. Начало добавления продуктов из отсортированного списка как 1, 2, 3 и т. д., пока тележка не заполнится.
5. Если изделие не может поместиться в корзину, пропустите его и выберите следующий возможный продукт из отсортированного списка.
6. После получения списка проверьте, может ли какой-либо продукт в выбранном списке заменить на другой продукт с меньшим объемом, но в результате получается больше значения корзины.

Но это не дает мне правильный список продуктов с максимальной стоимостью корзины. В чем проблема в вышеуказанной логике?

Answer 1

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

Ключевой трюк заключается в том, что вам нужно учитывать возможности, которые может быть ориентирована на несколько вариантов, а также количество способов выровнять собственные три измерения по трем осям тележки. Это 3! = 6 для трех измерений. Таким образом, при динамическом программировании при обработке i-го продукта, все 6 способов интерпретируют его 3 измерения как L, W, H.