Ciao a tutti, stavo provando a migliorare su DP e ho provato a fare supplì, ma ottengo solo 60/100.
Questo è il mio codice (spiego la mia logica sotto):
#include<bits/stdc++.h>
using namespace std;
vector<int> ris;
#define _showris for(auto it:ris) cout<<it<<" "; cout<<endl;
void buildTable(int index) //function to fill ris with the possible sums (mark with 1 the sums that can be made)
{
if(ris[index]==1) return;
ris[index]=1;
}
int main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int N; cin>>N; vector<int> V(N); for(int i=0; i<N; i++) cin>>V[i];
auto it=max_element(V.begin(), V.end());
int max=*it;
ris.resize(max+1, 0); //max+1 to use indexes from 1 to N, the last pos (ris[max] is not necessary)
ris[0]=1; ris[max]=1;
//initialize the vector with all the weights considering only one supplì of each kind:
for(int i=0; i<N-1; i++)
{
buildTable(V[i]);
}
for(int j=1; j<max; j++)
{
if(ris[j]==1)
{
for(int i=0; i<N; i++)
{
if(j+V[i]<=max)
buildTable(j+V[i]);
}
}
}
//_showris
for(int i=max; i>0; i--)
{
if(ris[i]==0)
{
cout<<i;
break;
}
}
}
in pratica io ho utilizzato (credo) la tecnica “tabulation” salvando tutte le possibili combinazioni in un vector ris, grande quanto il massimo valore dei minisupplì; infine, scorrendo il vector dalla fine trovo la più grande combinazione non possibile.
Spiegando la mia logica utilizzando un esempio:
vector V = {4, 7, 15}.
al primo for ris diventa {1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1}.
nel 2° for controllo ogni valore a 1 di ris e gli aggiungo i vari V[i] (x trovare le varie combinazioni):
ris ={1, 0, 0, 0, 1, 0, 0, 1, 1 (8=4+4), 0, 0, 1(11=7+4), 1(12=43), 0, 1(14=72), 1}.
scorrendo al contrario trovo così che il 13 è a 0(è la soluzione).
Potreste dirmi se è sbagliato qualcosa nel codice oppure se ho sbagliato l’interpretazione della consegna? Grazie mille per la disponibilità.