Mat_Menu 65/100


#1

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