Kaboobly Dooists visit the Canteen

Dynamic programming. Let $P[i][k][b]$ be the number of ways to choose $k$ items from the first $i$ tuples that cost exactly $b$ . Then, $P[0][0][0]=1$ and $P[i][k][b]=P[i-1][k][b]\sum_{j}P[i-1][k-1][b-A[i][j]]$ if the items in the $i$ -th tuple have costs $A[i][]$ . (The reason why this holds is quite clear: we either chose an item from the $i$ -th tuple or not; if we chose an item, the cost of all $k-1$ items chosen before it is $b-A[i][j]$ .)

Complexity: $O(NKB)$ if there are $N$ items in $T$ tuples, out of which we need to choose $K$ and the budget is $B$ , which is (pseudo)polynomial; the answer is $\sum_b{P[T][K][b]}$ .

By $\prod ( 1 + x^{a_1} y + x^{a_2} y )$ , do you mean $( 1 + x^{a_1} y + x^{a_2} y )( 1 + x^{b_1} y + x^{b_2} y )( 1 + x^{c_1} y + x^{c_2} y )\cdots( 1 + x^{j_1} y + x^{j_2} y )$

This is great! Pretty much what @bobbym none did, when Nick asked him the same question here

This is the code I ran, which gives me 9676686 as the answer. I don't know what's wrong with it. Anyone can help me? Thanks.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

//Backpack Problem
// The "KabooblyDooistsVisitTheCanteen" class.
public class KabooblyDooistsVisitTheCanteen
{
    public static void main (String[] args)
    {

        int count = 0; //counts number of possibilities
        int money = 50;

        int price[] = {12, 7, 10, 9, 7, 13, 11, 9, 8, 13, 10, 10, 8, 11, 11, 9, 7, 11, 9, 12};

        for (int i = 0 ; i < 20 ; i++)
        {
            money -= price [i];

            //System.out.println (price[i]);

            for (int j = 0 ; j < 20 ; j++)
            {
                if (j / 2 == i / 2) //You can only order at most one item from each tuple.
                {
                    continue;
                }
                money -= price [j];
                //System.out.println (" "+price[j]);
                for (int k = 0 ; k < 20 ; k++)
                {
                    if (k / 2 == j / 2 || k / 2 == i / 2)
                    {
                        continue;
                    }
                    money -= price [k];
                    //System.out.println ("  "+price[k]);
                    for (int l = 0 ; l < 20 ; l++)
                    {
                        if (l / 2 == k / 2 || l / 2 == j / 2 || l / 2 == i / 2)

                            {
                                continue;
                            }
                        money -= price [l];
                        for (int m = 0 ; m < 20 ; m++)
                        {
                            if (m / 2 == l / 2 || m / 2 == k / 2 || m / 2 == j / 2 || m / 2 == i / 2)
                            {
                                continue;
                            }
                            money -= price [m];
                            for (int n = 0 ; n < 20 ; n++)
                            {
                                if (n / 2 == m / 2 || n / 2 == l / 2 || n / 2 == k / 2 || n / 2 == j / 2 || n / 2 == i / 2)
                                {
                                    continue;
                                }
                                money -= price [n];
                                if (money >= 0) // check if money spent is under or equal to $50
                                {
                                    count++;
                                }
                                money = 50;

                            }
                        }
                    }
                }

            }
        }

        System.out.print (count);

    } // main method
} // KabooblyDooistsVisitTheCanteen class