제출 #1220770

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220770		renzo1805	Knapsack (NOI18_knapsack)	C++20	100 / 100	47 ms	3660 KiB

knapsack

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXC = 2005;

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

long long dp[2][MAXC];

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) );
   }
   
   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
   }
   
   // agora fazemos a programacao dinamica da mochila limitada
   int ant = 0, act = 1;
   for ( int j = 0; j <= C; ++j )
      dp[ant][j] = 0;
      
   n = (int) ListaItens.size();
   for ( int i = n - 1; i >= 0; --i ){
      w = ListaItens[i].peso;
      v = ListaItens[i].valor;
      b = ListaItens[i].qtd;
      for ( int j = 1; j <= C; ++j ){
         dp[act][j] = dp[ant][j]; // nao usamos o item
         for ( int k = 1; k <= b && k * w <= j; k++ )
            dp[act][j] = max( dp[act][j], dp[ant][j - k*w] + v*k );
      }
      swap( ant, act );
   }
   cout << dp[ant][C] << endl;
   return 0;
}

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