Рюкзак с весом и лимитом предметов

Question

Если у меня есть рюкзак с ограничением веса W, пункт Limit K и у меня есть N элементов, N >= k

Я знаю, как максимизировать его, имея массив трехмерного запоминания m[N][W][K] (N элементов для рассмотрения, W оставленный вес, K элементов для выбора) и, таким образом, сделать это в O(N * W * K) сложность, но есть ли способ сделать это еще быстрее в двумерном массиве запоминания и достичь более быстрой сложности, что-то вроде сложности O(N * W)?

Answer 1

Используемая вами пометка неверна: "m[N][W][K] (нужно учесть N пунктов, осталось W веса, осталось K элементов для выбора)". Он не фиксирует полную информацию о том, какие предметы оставлены на выбор, и сколько предметов осталось на выбор.

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