Tough Diophantine Equation

Izzhov

I was reading XKCD and I found this:
http://imgs.xkcd.com/comics/np_complete.png
I have no idea how to solve it. I know 7 orders of mixed fruit is one solution, but I only got that through trial and error. Does anyone know how to find every solution?

CompuChip

It's a knapsack problem, programming the most efficient way to solve it is a nice challenge

Izzhov

So... there isn't really any semi-efficient way to solve it by hand?

Vid

That's the million dollar question.

Izzhov

Ah, I see...

qubits135

For those who don't want to waste their time, the only other solution for this problem is 5.8+2.15+2*3.55=15.05




2.15
2.75
3.35
3.55

4.2
5.8

Needs 15.05

I scrutinized the combinations. It only applies to this problem.

1st, notice that, because 15.05 has a .05 in the end, we need an odd number of the orders ending in .x5 (the “odds”). So we need 1, 3, or 5 of them (7 is too much for any # but 2.15).

2nd, we investigate the 4.20 and the 5.80.

-Obviously, 3*5.8 exceeds the sum, 2*5.8=11.6 leaves us 3.45 to fill, which can’t be done.

-Then with 5.8, we have 9.25 to fill. Suppose we satisfy this with the “odds” (combination 5.8 and 4.2 will be considered later).
+ We must have an odd combination of the .x5 to make 9.25. Obviously, the 1 and 5 combinations can’t satisfy, so we need 3.
+ As 3*3.35=10.05 > 9.25 and 3*2.75=8.25<9.25, and 2*2.75 +3.55=9.05<9.25
hence we need two orders from the >3 orders , and 1 from the ones smaller than 3.
+ Try all these combinations (not that many of them), we see that only 2*3.55+2.15=9.25 does the trick!


-Now, consider 3*4.2=12.6, we need 2.45 not possible again.
-Then 2*4.2=8.4, we need 6.65, with 1 or 3 or 5 of the odd items. We can quickly drop this possibility.
-Then 4.2, we need 10.85. Observe that 3*3.55=10.65<10.85 hence no possible 3-combinations and 5*2.15=10.75no possible 5-combinations
-Now 4.2+5.8=10. We need 5.05 from 1, 3 or 5 of the odds. 3*2.15 is too big, and 1*3.55 is too small. Not possible.

3rd, we investigate the ones with only the odd prices. We can only have 5 of them.
5*2.75=13.75<15.05
5*3.35=16.75>15.05
We need something of the small side and the big side.

Suppose we have 3.55 in the combinations. As 5*3.55=17.75 which is 2.70 bigger than 15.05. We want to change some of the 3.55 to other elements to make a -2.70. Because the other elements are -.20, -.80,-1.40 less than 3.55, which can’t form a -2.70 . So no 3.55 in the combination.

4*3.35=13.4 is also too big for a 5-combination.
3*3.35=10.05 need 5 for 2 of the 2.15 and 2.75 can’t be done
2*3.35 + 3*2.75=14.95<15.05 No
Any other combination is too small

Izzhov

Thanks for the solution. :)