# Menù giapponese

**URL:** <https://forum.olinfo.it/t/menu-giapponese/3956>\
**Category:** Aiuto\
**Created:** [2 Settembre 2016, 2:25pm UTC](https://forum.olinfo.it/t/menu-giapponese/3956 "2016-09-02T14:25:23Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![yasser.fgs8](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/y/a183cd/32.png) [@yasser.fgs8](https://forum.olinfo.it/u/yasser.fgs8)\
**Post date:** [2 Settembre 2016, 2:25pm UTC](https://forum.olinfo.it/t/menu-giapponese/3956/1 "2016-09-02T14:25:23Z")

</div>

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:

```auto
#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](http://pastebin.com/a3m4CUgA) )

---

<div class="post-metadata">

**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\
**Post date:** [2 Settembre 2016, 3:46pm UTC](https://forum.olinfo.it/t/menu-giapponese/3956/2 "2016-09-02T15:46:26Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![filippos](https://forum.olinfo.it/user_avatar/forum.olinfo.it/filippos/32/103_2.png) [@filippos](https://forum.olinfo.it/u/filippos)\
**Post date:** [5 Settembre 2016, 3:39pm UTC](https://forum.olinfo.it/t/menu-giapponese/3956/3 "2016-09-05T15:39:21Z")

</div>

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](http://www.imparando.net/sito/olimpiadi_di_informatica/guida_quarta_edizione.pdf) 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 🙂

---

<div class="post-metadata">

**Author:** ![yasser.fgs8](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/y/a183cd/32.png) [@yasser.fgs8](https://forum.olinfo.it/u/yasser.fgs8)\
**Post date:** [6 Settembre 2016, 12:20pm UTC](https://forum.olinfo.it/t/menu-giapponese/3956/4 "2016-09-06T12:20:38Z")

</div>

grazie ad entrambi:grin: