Проблема в том, что при заданном наборе из n предметов и наборе из m рюкзаков, c [i] - вместимость рюкзака i, w [j] - вес предмета j, p [i] [j] - прибыль, которую положил предмет j в рюкзак i, это означает, что предмет может иметь разную прибыль, если положить его в другой рюкзак.
Мы должны найти оптимальное решение, чтобы общая прибыль выбранных предметов была максимальной, и все выбранные предметы должны быть помещены в один и тот же рюкзак. Например, если есть два ранца A и B, окончательное решение не может заключаться в том, чтобы поместить несколько предметов в A и поместить несколько предметов в B. Все выбранные предметы должны быть либо помещены в A, либо помещены в B. Так что этот вопрос несколько отличается из традиционной задачи о множественном ранце 0-1.
Одно из решений состоит в том, чтобы разбить эту проблему с множеством ранцев на несколько маленьких проблем с ранцем 0-1. Для каждого ранца мы можем использовать динамическое программирование, чтобы решить проблему ранца 0-1 и найти максимальную прибыль для этого ранца. Используйте тот же алгоритм, чтобы обойти все рюкзаки и выбрать максимальную прибыль ， мы можем получить решение, которое хотим.
Я хочу знать, есть ли лучший способ с большей сложностью времени для решения этой проблемы? Или какой-нибудь метод динамического программирования, чтобы избежать обхода всех рюкзаков? Если нет лучшего способа, как доказать?