У меня есть массив целых чисел.Обозначим это через A. Существует еще один массив W, содержащий веса, связанные с каждой записью A.
Другими словами, с каждой записью A [i] связан определенный весовой элемент W [i].(Обратите внимание, что весовые коэффициенты выходят за пределы ограниченного набора S_w = {w1, w2, w3, w4}, поэтому только несколько возможных значений)
Суть проблемы заключается в следующем: выбрать случайное количество записей из Aтак что при суммировании вы получите максимальное значение (SUM_A) при условии, что сумма их соответствующих весов (SUM_W) не превышает пороговое значение, W_threshold.
Одна из возможностей - это грубая сила: вычислить всеперестановки A и для каждой перестановки выберите первые n записей, чтобы их суммарный вес SUM_W не превышал W_threshold.Наконец, должна быть выбрана перестановка, которая дает максимум SUM_A.Но сложность этой схемы очень высока из-за шага вычисления перестановки, поскольку длина A не ограничена.
Еще одна (неоптимальная) возможность состоит в сортировке A в порядке убывания и затем выборе первых n записейтак что их SUM_W не превышает W_threshold.Это имеет меньшую сложность, но результат будет неоптимальным.
Может ли кто-нибудь дать мне советы, если у них уже есть алгоритм для решения вышеуказанной проблемы?Или, если у кого-то есть идеи лучше, чем те, которые я описал выше.Большое спасибо