Aiuto per Menù giapponese (mat_menu)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema Menù giapponese.

Ho provato a risolvere questo problema trattandolo come un knapsack, però ho due errori: nei primi 15 casi mi dice output errato (anche se provandolo sui casi di esempio mi dà un output corretto) e poi negli ultimi 5 casi mi dà errore di memoria. Capisco che la mia soluzione sia un po’ pesante però perché l’output è errato anche nei casi di test più leggeri?

Ecco il mio codice:

// INSERISCI QUI IL TU#include <bits/stdc++.h>
using namespace std;

void scelta(pair<int, vector<int>>& a, pair<int, vector<int>> c, pair<int, vector<int>> d, int e){
	if(c.first > d.first){
		a.first = c.first;
		a.second = c.second;
	}else{
		a.first = d.first + e;
		a.second = d.second;
		a.second.push_back(e);
	}
}

int main() {
	ifstream cin("input.txt");
	ofstream cout("output.txt");
	
	int N, W;
	cin >> N >> W;
	vector<int> weight(N);
	for(int i = 0; i < N; i++) cin >> weight[i];
	
	vector<vector<pair<int, vector<int>>>> dp(N + 1, vector<pair<int, vector<int>>>(W + 1, {0, {}}));
	for(int i = 1; i <= N; i++){
		for(int j = 1; j <= W; j++){
			if(j - weight[i - 1] < 0){
				dp[i][j].first = dp[i - 1][j].first;
				dp[i][j].second = dp[i - 1][j].second;
				continue;
			}
			
			scelta(dp[i][j], dp[i - 1][j], dp[i - 1][j - weight[i - 1]], weight[i - 1]);			
		}
	}
	
	for(int a : dp[N][W].second){
		cout << a << endl;
	}
	
	return 0;
}