Menù giapponese

Aiuto
1

Salve, ho tentato di risolvere questo problema ma ottengo solo 10/100 nonostante la soluzione sembra corretta e sul mio pc funziona. Potreste dirmi cosa ho sbagliato? Ecco il mio codice:

#include <iostream>
#include <stdio.h>
#include <algorithm>
 
int N;
int V, low=5000, ans=0, menu[5000];
 
void run(int coins, int mask)
{
    if(coins < 0) return;
 
    if(coins < low)
    {
        low = coins;
        ans = mask;
    }
 
    for(int i=0; i<N; i++)
    {
        if(!(mask & (1 << i)))
            run(coins-menu[i], mask | (1 << i));
    }
 
}
 
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    std::cin >> N >> V;
 
    for(int i=0; i<N; i++)
        std::cin >> menu[i];
 
    run(V, 0);
 
    for(int i=0; i<N; i++)
    {
        if(ans & (1 << i))
            std::cout << menu[i] << "\n";
    }
 
    return 0;
}

( http://pastebin.com/a3m4CUgA )

2

Penso che un possibile problema si trovi nell’istruzione (1 << i) quando i diventa molto grande…

3

Ad occhio, la tua soluzione ha una complessità esponenziale: se vuoi risolvere il problema ti conviene leggere qualcosa sulla programmazione dinamica e in particolare sul knapsack problem.

Per la programmazione dinamica, posso consigliarti la guida alle selezioni territoriali del professor Bugatti, mentre per il Knapsack non penso si trovi moltissimo in italiano ma dovresti farcela magari aiutandoti con qualche video su YouTube, ad esempio:

Per quanto riguarda il codice, mi pare di capire che utilizzi l’intero mask (32 bit) per indicare quali piatti siano presi e quali no, se è così allora la tua soluzione non può comunque funzionare per N > 32, mi sembra quindi normale che non totalizzi più di 10 punti e formuli un output sbagliato per alcuni dei testcase in cui non eccede il tempo limite, dovresti cercare un altro modo per gestire quali piatti fanno parte della soluzione :slight_smile:

4

grazie ad entrambi:grin: