Techgig July 2011 Expert level test cases

The expert level test cases were finally revealed today (Oct 4 2011) and I'm glad to see that I was right. The accepted solution was, in fact, sub-optimal. Here's a comparison of the expected output to the output produced by the Karmarkar-Karp algorithm:

#	Test case	Expected (Greedy)	Karmarkar-Karp
1	10:2:{2,3,10,5,8, 9,7,3,5,2}	{27,27}	0(5): {9 8 5 3 2 } : 27 1(5): {10 7 5 3 2 } : 27 Result: 27 27
2	17:2:{223,323,124,58,343, 34,85,73,232,74, 267,278,261,145,284, 447,3}	{1631,1623}	0(8): {447 284 278 261 223 73 58 3 } : 1627 1(9): {343 323 267 232 145 124 85 74 34 } : 1627 Result: 1627 1627
3	24:5:{2,3,10,5,8, 9,7,3,5,6, 2,4,6,3,4, 3,7,9,34,2, 3,5,3,2}	{40,27,26,26,26}	0(4): {34 2 2 2 } : 40 1(5): {8 7 5 4 3 } : 27 2(5): {9 7 5 3 2 } : 26 3(5): {9 6 5 3 3 } : 26 4(5): {10 6 4 3 3 } : 26 Result: 40 27 26 26 26
4	5:3:{10,20,90,200,100}	{200,110,110}	10 20 90 200 100 0(1): {200 } : 200 1(2): {90 20 } : 110 2(2): {100 10 } : 110 Result: 200 110 110
5	11:1:{23,43,10,56,38, 29,67,43,43,52, 22}	{426}	Result: 426
6	10:2:{1,1,1,1,9, 1,1,1,1,1}	{13,5}	0(5): {9 1 1 1 1 } : 13 1(5): {1 1 1 1 1 } : 5 Result: 13 5
7	34:7:{1,2,3,4,5, 6,7,8,9,10, 11,12,13,14,15, 16,21,53,74,346, 347,348,349,500,23, 25,26,27,47,6, 7,8,9,1}	{504,382,381,380,379, 164,163}	0(4): {500 2 1 1 } : 504 1(5): {346 14 8 8 4 } : 380 2(5): {349 12 10 7 3 } : 381 3(5): {348 11 9 7 6 } : 381 4(5): {347 13 9 6 5 } : 380 5(5): {74 27 26 21 16 } : 164 6(5): {53 47 25 23 15 } : 163 Result: 504 380 381 381 380 164 163
8	15:7:{1,2,3,4,5, 6,7,8,9,10, 11,12,13,14,51}	{52,19,17,17,17, 17,17}	0(2): {51 1 } : 52 1(3): {13 3 2 } : 18 2(2): {14 4 } : 18 3(2): {9 8 } : 17 4(2): {10 7 } : 17 5(2): {11 6 } : 17 6(2): {12 5 } : 17 Result: 52 18 18 17 17 17 17
9	25:8:{223,323,124,58,343, 34,85,73,232,74, 267,278,261,145,284, 447,3,1,2,3, 4,5,6,7,8}	{456,452,409,405,401, 397,392,378}	0(3): {232 223 1 } : 456 1(3): {447 2 3 } : 452 2(3): {261 145 4 } : 410 3(3): {323 73 5 } : 401 4(3): {343 58 3 } : 404 5(3): {278 74 34 } : 386 6(3): {267 124 6 } : 397 7(4): {284 85 8 7 } : 384 Result: 456 452 410 401 404 386 397 384

Test case #2 clearly shows, that the results produced by the Karmarkar-Karp algorithm are definitely better than the Greedy algorithm.