Зачем менять местами порядок рюкзаков на то же решение?
Насколько я знаю, в проблеме ранца используется динамическое программирование, чтобы найти лучшее решение для каждого элемента в зависимости от его предыдущих элементов. Эта гипотеза предполагает, что решение зависит от порядка элементов. Почему окончательное решение не зависит от заказа?
1 ответ
Нет. Решение динамического программирования для задачи о ранце не зависит от предыдущих пунктов.
При рассмотрении вопроса о том, положить предмет в рюкзак или нет, нам просто нужно рассмотреть оставшуюся емкость рюкзака до и после выбора предмета. Таким образом, мы проходим все возможные оставшиеся мощности и выбираем лучшую.
dp[i][c] = max(dp[i-1][c+w[i]] + v[i], dp[i-1][c])
где dp[i][c] указывает максимально возможное значение после рассмотрения i-го предмета с оставшейся емкостью рюкзака, равной c. w [i] указывает вес (или объем) i-го элемента, а v[i] указывает значение i-го элемента.
Нет необходимости рассматривать элементы по порядку. Рассматривать предметы по порядку просто для удобства. Вы также можете рассмотреть выбор элементов в обратном порядке или в случайном порядке.