Salve, sto provando a risolvere il problema mat_menu, ma ottengo solo 65/100, perchè in alcuni casi a quanto pare stampo numeri che non corrispondono a nessun piatto. Allego il mio codice, che consiste in pratica in una dp su una matrice che calcola tutte le possibile somme e se minori del budget le salva. In più utilizzo un altro array che all’indice i tiene conto di quale elemento è stato aggiunto per ultimo quando è stata trovata la somma i. Grazie per l’aiuto.
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
int n,b;
int v[6000];
bool tab[6000][6000];
int co[10000];
int main(){
cin>>n>>b;
for(int i=0;i<n;i++){
cin>>v[i];
for(int y=0;y<5100;y++)tab[i][y]=false;
}
int mas=0;
tab[0][0]=true;
tab[0][v[0]]=true;
for(int i=0;i<10000;i++){
co[i]=-1;
}
co[0]=0;
co[v[0]]=v[0];
if(v[0]<=b){
mas=max(mas, v[0]);
}
for(int i=1;i<n;i++){
for(int y=0;y<5100;y++){
if(tab[i-1][y]==true){
tab[i][y]=true;
tab[i][v[i]+y]=true;
if(v[i]+y<=b){
mas=max(mas, v[i]+y);
}
if(co[v[i]+y]==-1)co[v[i]+y]=v[i];
}
}
}
int x=mas;
while(x>0){
cout<<co[x]<<endl;
x-=co[x];
}
}