제출 #1220799

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220799		pauloaph	Knapsack (NOI18_knapsack)	C++20	100 / 100	38 ms	4064 KiB

knapsack

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct item {
  long long valor;
  long long peso;
  long long qtd;
  item() {}
  item(long long v, long long p, long long q) {
    valor = v;
    peso = p;
    qtd = q;
  }
};

bool cmp(const item &A, const item &B) { return A.valor > B.valor; }

int main() {

  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int C;
  int n;

  cin >> C >> n;
  // entre todos com peso w, so precisamos considerar os mais valiosos C / w
  // elementos
  long long v, w, b;
  vector<long long> Limite(C + 1, 0);

  for (int i = 1; i <= C; ++i)
    Limite[i] =
        C / i; // esse eh o num. maximo de itens que podemos usar de peso i

  vector<item> I;
  for (int i = 0; i < n; i++) {
    cin >> v >> w >> b;
    if (w <= C)
      I.push_back(item(v, w, b));
  }
  // ordenamos para considerar os itens de maior valor primeiro
  sort(I.begin(), I.end(), cmp);
  // agora vou criar outro vetor de itens so com os que vou considerar
  vector<item> ListaItens;
  for (int i = 0; i < (int)I.size(); ++i) {
    v = I[i].valor;
    w = I[i].peso;
    b = I[i].qtd;

    if (Limite[w] == 0)
      continue; // nao precisa mais considerar esse peso

    // ajustamos a quantidade
    b = min(b, Limite[w]);
    ListaItens.push_back(item(v, w, b));
    Limite[w] -= b; // reduzimos o limite
  }

  n = (int)ListaItens.size();
  // agora fazemos a programacao dinamica da mochila limitada
  /*

     completar

  */

  vector<long long> NW, NV;

  for (int i = 0; i < n; i++) {
    int x = 1;
    while (ListaItens[i].qtd > x) {
      ListaItens[i].qtd -= x;
      NW.push_back(x * ListaItens[i].peso);
      NV.push_back(x * ListaItens[i].valor);
      x = x << 1;
    }
    NW.push_back(ListaItens[i].peso * ListaItens[i].qtd);
    NV.push_back(ListaItens[i].valor * ListaItens[i].qtd);
  }

  long long dp[2][C + 1];
  int prev = 0, act = 1;
  // caso base : quando nao temos mais itens
  for (int c = 0; c <= C; c++)
    dp[prev][c] = 0;

  for (int i = NW.size() - 1; i >= 0; i--) {
    for (int c = 0; c <= C; c++) {
      dp[act][c] = dp[prev][c];
      if (NW[i] <= c) {
        dp[act][c] = max(dp[act][c], dp[prev][c - NW[i]] + NV[i]);
      }
    }
    swap(act, prev);
  }

  cout << dp[prev][C] << endl;
  return 0;
}

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