Динамическое программирование: космические корабли и космические камни

Заявление о проблеме

Шахтер Грант заметил несколько ценных астероидов в поясе Койпера. Он хотел бы полетать на своем космическом корабле, подобрать несколько астероидов и вернуться на Землю, чтобы продать их. Каждый из M астероидов имеет вес W_i и значение V_i.

У космического корабля Гранта пока нет двигателей. Он может купить любое количество из N двигателей для продажи, каждый со своим лифтом L_i и стоимостью C_i. Чтобы вернуть астероиды, ракета должна иметь общую подъемную силу больше или равную весу астероидов.

Какую максимальную прибыль может получить Грант?

Чтобы увидеть или попытаться решить проблему полностью, зарегистрируйтесь здесь, затем нажмите здесь.

Решение

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

Хотя работа с двумя отдельными объектами может показаться сложной, обратите внимание, что эти два объекта могут быть смоделированы как один и тот же объект, каждый с заданным подъемом и прибылью. Двигатели имеют положительную подъемную силу и отрицательную прибыль, в то время как астероиды имеют отрицательную подъемную силу и положительную прибыль. Таким образом, мы можем упростить это до задачи о рюкзаке 0–1, где мы должны найти максимальную прибыль для любого неотрицательного подъема.

Как правило, у нас есть несколько вариантов ранца 0–1, исчерпывающий поиск, где проверяются все возможности, и решение динамического программирования (DP). Существует N + M ≤ 2000 различных элементов, поэтому при тщательном поиске можно оценить 2² возможных варианта, что слишком много, чтобы выполнить его вовремя. Мы уверены, что общий вес и общая подъемная сила не превысят 100 000, и, посчитав, мы можем обнаружить, что общие затраты / прибыль могут достигать миллиарда. Это означает, что мы должны использовать более эффективное решение динамического программирования с состоянием в качестве чистой прибыли, максимизируя связанную с этим прибыль.

Мы инициализируем наш массив DP со всеми значениями подъема, связанными с отрицательной бесконечностью (2²⁹) прибыли. Свяжите нулевое значение подъемной силы с нулевой прибылью. Затем мы можем обновить массив DP в соответствии с каждым движком, чтобы массив отражал максимально возможное значение прибыли. Затем таким же образом обновите массив для каждого астероида. Наконец, мы сканируем все значения подъема, включая ноль, чтобы определить максимальную общую прибыль.

Код

Ниже мое решение на C ++.

#include<iostream>
#define INF (1<<29)
using namespace std;
int n, m, w, c, ans;
int dp[100000];//dp[net lift] = profit
int main() {
   //initialize dp array
   for (int i = 1; i < 100000; i++) dp[i] =- INF;
   
   //take inputs
   cin >> n >> m;
   
   //take in/enter rockets
   for (int i = 0; i < n; i++) {
      cin >> w >> c;
      for (int j = 100000 - w - 1; j >= 0; j--) {
         if (dp[j] != -INF) dp[j + w] = max(dp[j + w], dp[j] - c);
      }
   }
   
   //take in/enter asteroids
   for (int i = 0; i < m; i++) {
      cin >> w >> c;
      for (int j = w; j < 100000; j++) {
         if (dp[j] != -INF) dp[j - w] = max(dp[j - w], dp[j] + c);
      }
   }
   
   //find the maximum profit
   for (int i = 0; i < 100000; i++) ans = max(ans,dp[i]);
   cout << ans << endl;
}