Submission #1219412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219412		alessandrojean	Knapsack (NOI18_knapsack)	C++20	73 / 100	158 ms	327680 KiB

knapsack

#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

const int MAX_N = 100000;
const int MAX_S = 2000;

int S;
int N;
int V[MAX_N];
int W[MAX_N];
int K[MAX_N];
int dp[MAX_N][MAX_S + 1];

// Valores dos itens "novos".
int NV[MAX_N];
// Pesos dos itens "novos".
int NW[MAX_N];
// Total dos itens "novos".
int m = 0;

class MaxQueue {
  private:
    deque<pair<int, int>> Q;
    int time_added;
    int time_removed;
    int delta;

  public:
    MaxQueue() {
      delta = time_added = time_removed = 0;
    }

    void push(int x) {
      int x_delta = x - delta;

      while (!Q.empty() && Q.back().first < x_delta) {
        Q.pop_back();
      }

      Q.push_back({x_delta, time_added++});
    }

    void pop() {
      if (Q.empty()) {
        return;
      }

      if (time_removed == Q.front().second) {
        Q.pop_front();
      }

      time_removed++;
    }

    int max() {
      return Q.front().first + delta;
    }

    void add_all(int d) {
      delta += d;
    }
};

/**
 * Baseado na solução apresentada em sala de aula para
 * o problema da mochila limitada em 11/06.
 */
int find_best_solution() {
  // Primeiro passo: agrupar em potencias de dois + resto.
  for (int i = 0; i < N; i++) {
    int pos = 0;

    while ((1 << pos) < K[i]) {
      NW[m] = (1 << pos) * W[i];
      NV[m] = (1 << pos) * V[i];

      K[i] -= (1 << pos);
      pos++;
      m++;
    }

    if (K[i] > 0) {
      NW[m] = K[i] * W[i];
      NV[m] = K[i] * V[i];
      m++;
    }
  }

  // Segundo passo: usar o problema da mochila normal
  // com os novos pesos e valores.
  for (int c = 0; c <= S; c++) {
    dp[m][c] = 0;
  }

  for (int i = m - 1; i >= 0; i--) {
    for (int c = 0; c <= S; c++) {
      // Não pegar o elemento.
      dp[i][c] = dp[i + 1][c];

      if (NW[i] <= c) {
        dp[i][c] = max(dp[i][c], NV[i] + dp[i + 1][c - NW[i]]);
      }
    }
  }

  return dp[0][S];
}

/**
 * Difícil achar referências que usem a fila do jeito que foi passado em aula,
 * mas estes links comentam da ideia da janela deslizante.
 * 
 * Referências:
 * - https://cp-algorithms.com/dynamic_programming/knapsack.html
 * - https://books.google.com.br/books?id=u5DB7gck08YC&lpg=PA211&pg=PA194&redir_esc=y#v=onepage&q&f=false
 * - https://dhruvbird.blogspot.com/2011/09/integer-01-bounded-knapsack-problem.html
 * - https://blog.mitrichev.ch/2011/07/integral-bounded-knapsack-problem.html
 * - https://programming.vip/docs/monotone-queue-optimization-for-multiple-knapsack-problems.html
 */
int find_best_solution_sliding_window() {
  for (int i = N - 1; i >= 0; i--) {
    // Itera sobre todos as possíveis classes de W[i]. Vai só até W[i] - 1
    // pois sempre vai ter um rest e um mult tal que color + mult * W[i] = S.
    for (int color = 0; color < W[i]; color++) {
      // Cada classe tem sua fila.
      MaxQueue queue;
      int window_size = 0;

      // Itera entre os próximos casos da mesma classe.
      for (int mult = 0; color + mult * W[i] <= S; mult++) {
        queue.add_all(V[i]);
        queue.push(dp[i + 1][color + mult * W[i]]);

        // Chegou ao limite de itens, precisa avançar a janela.
        if (++window_size > K[i] + 1) {
          queue.pop();
          window_size--;
        }

        dp[i][color + mult * W[i]] = queue.max();
      }
    }
  }

  return dp[0][S];
}

int main(int argc, char * argv[]) {
  cin >> S >> N;

  for (int i = 0; i < N; i++) {
    cin >> V[i] >> W[i] >> K[i];
  }

  cout << find_best_solution_sliding_window() << '\n';

  return EXIT_SUCCESS;
}

• Subtask 1: 12 / 12
• Subtask 2: 17 / 17
• Subtask 3: 20 / 20
• Subtask 4: 24 / 24
• Subtask 5: 0 / 27