제출 #1219447

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219447		alessandrojean	Knapsack (NOI18_knapsack)	C++20	73 / 100	1095 ms	472 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; // int V[MAX_N];
// int * W; // int W[MAX_N];
// int * K; // int K[MAX_N];
int dp[2][MAX_S + 1]; // int dp[MAX_N][MAX_S + 1];

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;
    }
};

/**
 * 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. Complexidade O(N * S).
 * 
 * Como S <= 2000, o ideal seria usar algum algoritmo guloso provavelmente.
 * - https://pastebin.com/E69ffwxd
 * - https://usaco.guide/problems/noi-knapsack/solution
 * 
 * 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() {
  int ant = 0, act = 1;
  int v_i, w_i, k_i;

  for (int i = N - 1; i >= 0; i--) {
    // Lê aqui para evitar N iterações a mais.
    // Lendo aqui não precisa do vetor também.
    // cin >> V[i] >> W[i] >> K[i];
    cin >> v_i >> w_i >> k_i;

    // Tem casos de teste que W[i] pode ser maior que S.
    // Como nem caberia na mochila, pode pular direto.
    if (w_i > S) {
      continue;
    }

    // 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 k = 0;

      // Itera entre os próximos casos da mesma classe.
      for (int mult = 0; color + mult * w_i <= S; mult++) {
        int c = color + mult * w_i;

        queue.add_all(v_i);
        queue.push(dp[ant][c]);

        // Chegou ao limite de itens, precisa avançar a janela.
        if (++k > k_i + 1) {
          queue.pop();
          k--;
        }

        dp[act][c] = queue.max();
      }
    }

    swap(act, ant);
  }

  return dp[ant][S];
}

int main(int argc, char * argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  
  cin >> S >> N;

  // V = new int[N];
  // W = new int[N];
  // K = new int[N];

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

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

  // delete [] V;
  // delete [] W;
  // delete [] K;

  return EXIT_SUCCESS;
}

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