\n
\r\nInput positions\r\n\r\nID MIN_PLAYERS MAX_PLAYERS\r\n-- ----------- -----------\r\nAL 12 12\r\nCB 2 3\r\nCO 1 1\r\nFW 1 3\r\nGK 1 1\r\nMF 3 5\r\nWB 0 2\r\n\r\n6 rows selected.\r\n\r\nInput players\r\n\r\nID CLUB_NAME PLAYER_NAME PO PRICE AVG_POINTS APPEARANCES PRF_R VFP_R PRC_R\r\n--- ------------------------------ ------------------------------ -- ---------- ---------- ----------- ---------- ---------- ----------\r\n038 Portuguesa Ivan WB 755 1320 100 1 2 20\r\n001 Atl\u00e9tico-PR \u00c9derson FW 1712 1012 500 2 22 97\r\n002 Vit\u00f3ria Maxi Biancucchi FW 1962 1005 400 3 33 103\r\n003 Fluminense Rafael Sobis FW 2303 955 400 4 47 112\r\n098 Fluminense Dig\u00e3o CB 931 927 300 5 5 34\r\n058 Internacional Fred MF 3028 892 500 6 92 114\r\n059 Gr\u00eamio Z\u00e9 Roberto MF 2593 878 400 7 73 113\r\n039 Vasco Elsinho WB 1468 850 400 8 25 83\r\n004 Bahia Fernand\u00e3o FW 1328 822 500 9 19 70\r\n060 Internacional Otavinho MF 762 807 300 10 4 21\r\n078 Flamengo Jaime De AlMFda CO 1156 803 100 11 12 52\r\n022 Vit\u00f3ria Wilson GK 1239 794 500 12 17 59\r\n021 Cruzeiro F\u00e1bio GK 2090 794 500 12 59 106\r\n023 Coritiba Vanderlei GK 1858 776 500 14 45 101\r\n005 S\u00e3o Paulo Luis Fabiano FW 2154 758 400 15 67 107\r\n040 Cruzeiro Eg\u00eddio WB 1482 752 500 16 34 84\r\n041 Fluminense Carlinhos WB 1240 693 300 17 26 60\r\n099 Flamengo Samir CB 267 680 100 18 1 1\r\n061 Vasco Carlos Alberto MF 1501 675 200 19 42 85\r\n006 Botafogo Rafael Marques FW 1974 668 500 20 74 105\r\n062 Cruzeiro Nilton MF 2239 646 500 21 95 110\r\n100 Cruzeiro Ded\u00e9 CB 2254 640 500 22 97 111\r\n063 Coritiba J\u00fanior Urso MF 1438 622 500 23 43 81\r\n064 Crisci\u00fama Jo\u00e3o Vitor MF 1327 604 500 24 41 69\r\n101 S\u00e3o Paulo L\u00facio CB 2171 602 500 25 99 108\r\n007 Cruzeiro Dagoberto FW 2211 594 500 26 102 109\r\n102 Gr\u00eamio Bressan CB 1085 590 400 27 28 48\r\n103 Atl\u00e9tico-PR Manoel CB 1699 588 500 28 70 96\r\n065 Corinthians Guilherme MF 883 587 400 29 14 32\r\n104 Ponte Preta Cl\u00e9ber CB 1461 578 500 30 55 82\r\n008 N\u00e1utico Rog\u00e9rio FW 1062 570 500 31 29 44\r\n066 Corinthians Ralf MF 1965 570 500 31 93 104\r\n067 Vit\u00f3ria Escudero MF 1638 568 500 33 68 93\r\n068 Portuguesa Correa MF 844 560 400 34 15 26\r\n042 N\u00e1utico Auremir WB 773 548 400 35 11 22\r\n079 Cruzeiro Marcelo Oliveira CO 1611 543 500 36 75 92\r\n080 Fluminense Abel Braga CO 1751 536 400 37 84 98\r\n105 Cruzeiro Bruno Rodrigo CB 1547 528 500 38 72 88\r\n043 Cruzeiro Mayke WB 374 525 200 39 3 3\r\n069 Portuguesa Souza MF 1262 517 400 40 49 62\r\n070 Coritiba Alex MF 1698 508 500 41 88 95\r\n009 Flamengo Hernane FW 1387 498 500 42 65 75\r\n071 Gr\u00eamio Souza MF 1380 498 400 42 64 74\r\n106 Santos Edu Dracena CB 1682 497 300 44 90 94\r\n010 Crisci\u00fama Lins FW 1840 490 500 45 103 100\r\n011 Santos Neilton FW 638 488 400 46 9 11\r\n012 Fluminense Samuel FW 1001 487 300 47 36 37\r\n072 Ponte Preta Cicinho MF 1142 472 500 48 48 51\r\n024 Atl\u00e9tico-MG Victor GK 1163 467 400 49 52 53\r\n045 Atl\u00e9tico-MG Richarlyson WB 1020 467 300 49 40 38\r\n044 Portuguesa Luis Ricardo WB 858 467 300 49 27 28\r\n013 Ponte Preta Chiquinho FW 997 464 500 52 38 36\r\n081 Internacional Dunga CO 1422 463 500 53 79 80\r\n047 S\u00e3o Paulo Juan WB 789 457 300 54 24 23\r\n046 Internacional Fabr\u00edcio WB 876 457 400 54 31 30\r\n014 Atl\u00e9tico-MG Luan FW 1318 455 400 56 71 67\r\n048 S\u00e3o Paulo Paulo Miranda WB 1053 454 500 57 44 41\r\n049 Flamengo Jo\u00e3o Paulo WB 715 453 300 58 18 19\r\n050 S\u00e3o Paulo Rodrigo Caio WB 1192 452 500 59 60 56\r\n025 Bahia Marcelo Lomba GK 1364 450 500 60 78 71\r\n073 Botafogo Fellype Gabriel MF 860 447 400 61 32 29\r\n082 Vit\u00f3ria Caio J\u00fanior CO 1140 445 500 62 56 50\r\n015 Ponte Preta William FW 1393 444 500 63 81 76\r\n107 N\u00e1utico William Alves CB 556 443 300 64 8 8\r\n083 Gr\u00eamio Vanderlei Luxemburgo CO 1577 442 400 65 98 89\r\n084 S\u00e3o Paulo Ney Franco CO 1515 439 500 66 94 86\r\n074 Atl\u00e9tico-PR Jo\u00e3o Paulo MF 1056 438 500 67 46 42\r\n026 Botafogo Renan GK 677 437 400 68 16 13\r\n075 Vasco Sandro Silva MF 1076 428 500 69 53 46\r\n108 Fluminense Gum CB 1218 422 400 70 69 58\r\n085 N\u00e1utico Levi Gomes CO 708 420 200 71 21 18\r\n109 Flamengo Wallace CB 429 420 200 71 6 4\r\n051 Coritiba Victor Ferraz WB 1304 420 500 71 80 65\r\n076 Santos C\u00edcero MF 1415 418 500 74 91 78\r\n027 Flamengo Felipe GK 1526 414 500 75 101 87\r\n077 Fluminense Wagner MF 855 413 300 76 37 27\r\n052 Bahia Jussandro WB 694 410 500 77 23 16\r\n110 N\u00e1utico Jo\u00e3o Filipe CB 547 410 400 77 10 7\r\n016 Botafogo Vitinho FW 1020 404 500 79 54 38\r\n053 Santos Rafael Galhardo WB 1288 404 500 79 83 64\r\n111 Gr\u00eamio Werley CB 1590 403 400 81 105 90\r\n055 N\u00e1utico Maranh\u00e3o WB 653 402 500 82 20 12\r\n054 Goi\u00e1s William Matheus WB 587 402 500 82 13 9\r\n112 Corinthians Gil CB 1323 398 500 84 85 68\r\n113 Vit\u00f3ria Gabriel Paulista CB 1177 394 500 85 76 54\r\n086 Atl\u00e9tico-PR Ricardo Drubscky CO 796 392 500 86 35 24\r\n087 Coritiba Marquinhos Santos CO 1059 389 500 87 62 43\r\n017 Coritiba Deivid FW 1590 376 500 88 107 90\r\n028 Gr\u00eamio Dida GK 1132 375 400 89 77 49\r\n114 Goi\u00e1s Ernando CB 1024 374 500 90 63 40\r\n029 Corinthians C\u00e1ssio GK 1251 374 500 90 89 61\r\n018 Gr\u00eamio Barcos FW 1896 367 400 92 110 102\r\n088 Vasco Paulo Autuori CO 1313 361 500 93 100 66\r\n030 Vasco Michel Alves GK 899 348 500 94 57 33\r\n019 Atl\u00e9tico-MG J\u00f4 FW 1393 340 200 95 106 76\r\n056 Internacional Gabriel WB 1181 338 500 96 96 55\r\n057 Goi\u00e1s V\u00edtor WB 877 336 500 97 58 31\r\n089 Portuguesa Edson Pimenta CO 367 326 400 98 7 2\r\n090 Botafogo Oswaldo De Oliveira CO 1077 323 500 99 87 47\r\n031 Crisci\u00fama Bruno GK 1066 320 500 100 86 45\r\n092 Santos Claudinei Oliveira CO 1192 317 300 101 104 56\r\n091 Corinthians Tite CO 1368 317 500 101 108 73\r\n020 S\u00e3o Paulo Osvaldo FW 1364 312 500 103 109 71\r\n032 Internacional Muriel GK 981 310 400 104 82 35\r\n033 Santos Rafael GK 1782 300 500 105 112 99\r\n093 Bahia Crist\u00f3v\u00e3o Borges CO 827 292 500 106 66 25\r\n094 Crisci\u00fama Vad\u00e3o CO 704 286 500 107 50 17\r\n095 Goi\u00e1s Enderson Moreira CO 680 253 500 108 61 14\r\n034 Atl\u00e9tico-PR Weverton GK 616 248 500 109 51 10\r\n035 Fluminense Ricardo Berna GK 460 242 400 110 30 6\r\n096 Atl\u00e9tico-MG Cuca CO 1262 232 400 111 111 62\r\n036 Portuguesa Gledson GK 452 210 400 112 39 5\r\n037 S\u00e3o Paulo Rog\u00e9rio Ceni GK 1420 117 400 113 114 79\r\n097 Ponte Preta Z\u00e9 S\u00e9rgio CO 685 75 100 114 113 15\r\n\r\n114 rows selected.\r\n<\/pre>\n<\/div>\nNote that I dropped the poster’s formations based data model in favour of the above, more general one. I used AL as a code for team size, and chose the maximum price arbitrarily (but having an influence on results). I also multiplied the points and prices by a factor of 100 to allow me to work in integers.<\/p>\n
Test Problem 2: English Premier League<\/em>
\nThe second problem is be based on English Premier League and I got the data from a ‘scraping’ web-site, https:\/\/scraperwiki.com\/scrapers\/fantasy_premier_league_player_stats\/. There are some data quality issues with the data, but it is good enough for technical testing. I summed the players’ points over the last season and took their values at the last week as prices.<\/p>\nAfter excluding zero-point players, there remained 576 players, of five positions, with eleven players forming a team, and the problem is the same, with the positional constraints:<\/p>\n
\n
\r\nInput positions\r\n\r\nID MIN_PLAYERS MAX_PLAYERS\r\n-- ----------- -----------\r\nAL 11 11\r\nDF 3 5\r\nFW 1 3\r\nGK 1 1\r\nMF 2 5\r\n\r\nInput players\r\n\r\n ID CLUB_NAME PLAYER_NAME PO PRICE AVG_POINTS APPEARANCES PRF_R VFP_R PRC_R\r\n---------- --------------- -------------------- -- ---------- ---------- ----------- ---------- ---------- ----------\r\n 661 Tottenham Gareth Bale MF 111 240 38 1 36 573\r\n 286 Liverpool Luis Suarez FW 105 213 38 2 62 572\r\n 30 Arsenal Santi Santi Cazorla MF 97 198 36 3 57 569\r\n 149 Chelsea Juan Mata MF 102 190 36 4 90 571\r\n 265 Liverpool Steven Gerrard MF 92 187 38 5 60 562\r\n 533 Southampton Rickie Lambert FW 69 178 37 6 5 513\r\n 165 Everton Leighton Baines DF 78 173 38 7 25 537\r\n 318 Man City Carlos Tevez FW 92 172 38 8 87 562\r\n 139 Chelsea Eden Hazard MF 96 171 35 9 99 568\r\n 641 Swansea Miguel Michu MF 79 169 36 10 41 542\r\n 177 Everton Marouane Fellaini MF 73 168 38 11 14 527\r\n 47 Aston Villa Christian Benteke FW 74 166 35 12 20 530\r\n 204 Fulham Dimitar Berbatov FW 71 161 37 13 18 523\r\n 720 West Brom Romelu Lukaku FW 66 157 37 14 8 498\r\n 314 Man City David Silva MF 92 154 38 15 117 562\r\n 298 Man City Joe Hart GK 69 154 38 15 22 513\r\n 549 Stoke City Asmir Begovic GK 56 154 40 15 1 421\r\n 428 Norwich Robert Snodgrass MF 62 152 38 18 7 474\r\n 332 Man Utd Patrice Evra DF 73 152 38 18 51 527\r\n 126 Chelsea Demba Ba FW 78 149 37 20 77 537\r\n 616 Sunderland Stephane Sessegnon MF 67 148 38 21 26 504\r\n 575 Stoke City Jonathan Walters MF 63 147 40 22 13 482\r\n 770 West Ham Kevin Nolan MF 61 145 36 23 9 465\r\n 354 Man Utd Wayne Rooney FW 116 141 37 24 201 575\r\n 322 Man City Yaya Yaya Toure MF 82 141 37 24 108 548\r\n 268 Liverpool Glen Johnson DF 65 141 37 24 35 491\r\n 760 West Ham Jussi Jaaskelainen GK 52 139 36 27 2 361\r\n 198 Everton Steven Pienaar MF 66 139 38 27 46 498\r\n 609 Sunderland Simon Mignolet GK 53 139 38 27 3 379\r\n 598 Sunderland Adam Johnson MF 68 138 37 30 61 508\r\n 726 West Brom James Morrison MF 57 135 39 31 11 429\r\n 569 Stoke City Ryan Shawcross DF 56 133 40 32 10 421\r\n 248 Liverpool Daniel Agger DF 64 133 38 32 52 488\r\n 270 Liverpool Sanchez Jose Enrique DF 61 133 37 32 33 465\r\n 239 Fulham Mark Schwarzer GK 51 133 38 32 4 344\r\n 800 Wigan Arouna Kone FW 69 131 37 36 78 513\r\n 684 Tottenham Aaron Lennon MF 71 131 38 36 91 523\r\n 161 Chelsea Fernando Torres FW 93 131 36 36 165 566\r\n 552 Stoke City Peter Crouch FW 60 131 40 36 31 458\r\n 594 Sunderland Steven Fletcher FW 67 131 36 36 71 504\r\n 295 Man City Edin Dzeko FW 68 130 38 41 76 508\r\n 700 Tottenham Jan Vertonghen DF 68 129 37 42 80 508\r\n 132 Chelsea Petr Cech GK 64 129 38 42 64 488\r\n 144 Chelsea Frank Lampard MF 85 128 36 44 150 553\r\n 289 Man City Sergio Aguero FW 111 127 39 45 217 573\r\n 278 Liverpool Jose Reina GK 58 126 38 46 34 438\r\n 628 Swansea Jonathan De Guzman MF 57 122 36 47 39 429\r\n 667 Tottenham Jermain Defoe FW 79 122 37 47 137 542\r\n 723 West Brom Gareth McAuley DF 52 122 38 47 12 361\r\n 802 Wigan Shaun Maloney MF 54 121 37 50 21 395\r\n 405 Norwich Sebastien Bassong DF 53 121 37 50 16 379\r\n 186 Everton Phil Jagielka DF 59 120 38 52 59 449\r\n 558 Stoke City Robert Huth DF 55 120 40 52 32 409\r\n 353 Man Utd Rafael Rafael DF 61 119 38 54 72 465\r\n 771 West Ham Joey O'Brien DF 48 119 36 54 6 269\r\n 196 Everton Leon Osman MF 62 119 37 54 75 474\r\n 650 Swansea Wayne Routledge MF 53 118 36 57 24 379\r\n 323 Man City Pablo Zabaleta DF 64 117 38 58 92 488\r\n 669 Tottenham Clint Dempsey MF 89 116 37 59 186 557\r\n 612 Sunderland John O'Shea DF 51 115 38 60 19 344\r\n 374 Newcastle Papiss Cisse FW 87 115 39 60 182 556\r\n 142 Chelsea Branislav Ivanovic DF 69 114 36 62 120 513\r\n 211 Fulham Damien Duff MF 58 114 38 62 69 438\r\n 364 Man Utd David de Gea GK 58 114 38 62 69 438\r\n 185 Everton Tim Howard GK 53 113 38 65 43 379\r\n 154 Chelsea Emboaba Oscar MF 79 113 35 65 163 542\r\n 602 Sunderland Sebastian Larsson MF 59 112 38 67 79 449\r\n 719 West Brom Shane Long FW 58 110 38 68 81 438\r\n 413 Norwich Grant Holt FW 59 110 38 68 89 449\r\n 713 West Brom Ben Foster GK 51 109 39 70 42 344\r\n 536 Southampton Jason Puncheon MF 47 107 37 71 17 238\r\n 232 Fulham Sascha Riether DF 48 107 37 71 23 269\r\n 145 Chelsea David Luiz DF 67 107 36 71 132 504\r\n 784 Wigan Jean Beausejour MF 53 106 38 74 65 379\r\n 60 Aston Villa Bradley Guzan GK 48 106 38 74 27 269\r\n 293 Man City Gael Clichy DF 58 106 38 74 93 438\r\n 476 QPR Adel Taarabt MF 53 105 38 77 66 379\r\n 804 Wigan James McCarthy MF 48 105 38 77 30 269\r\n 595 Sunderland Craig Gardner MF 49 104 38 79 44 293\r\n 131 Chelsea Gary Cahill DF 60 104 38 79 106 458\r\n 423 Norwich Anthony Pilkington MF 55 104 38 79 82 409\r\n 541 Southampton Morgan Schneiderlin MF 48 103 37 82 38 269\r\n 412 Norwich Javier Garrido DF 47 103 38 82 29 238\r\n 414 Norwich Wes Hoolahan MF 55 103 38 82 86 409\r\n 134 Chelsea Ashley Cole A DF 63 103 36 82 123 482\r\n 701 Tottenham Kyle Walker DF 61 103 37 82 115 465\r\n 540 Southampton Jay Rodriguez FW 52 103 37 82 67 361\r\n 173 Everton Sylvain Distin DF 54 102 38 88 83 395\r\n 236 Fulham Bryan Ruiz FW 50 102 38 88 58 313\r\n 501 Reading Jobi McAnuff MF 47 101 36 90 37 238\r\n 776 West Ham Winston Reid DF 48 101 36 90 47 269\r\n 576 Stoke City Glenn Whelan MF 49 101 40 90 54 293\r\n 233 Fulham John Arne Riise DF 52 100 38 93 74 361\r\n 358 Man Utd Antonio Valencia MF 82 100 38 93 200 548\r\n 331 Man Utd Jonny Evans J DF 53 99 37 95 88 379\r\n 285 Liverpool Daniel Sturridge FW 74 99 35 95 178 530\r\n 187 Everton Nikica Jelavic FW 77 98 37 97 190 534\r\n 498 Reading Adam Le Fondre FW 44 97 36 98 28 156\r\n 261 Liverpool Stewart Downing MF 57 97 37 98 109 429\r\n 417 Norwich Bradley Johnson MF 47 97 38 98 53 238\r\n 420 Norwich Russell Martin R DF 42 96 38 101 15 82\r\n 648 Swansea Angel Rangel DF 47 96 36 101 56 238\r\n 769 West Ham Mark Noble MF 46 96 36 101 50 216\r\n 267 Liverpool Jordan Henderson MF 48 95 38 104 68 269\r\n 156 Chelsea Nascimento Ramires MF 62 95 35 104 140 474\r\n 635 Swansea Pablo Hernandez MF 59 95 33 104 130 449\r\n 606 Sunderland James McClean MF 56 95 39 104 111 421\r\n 372 Newcastle Yohan Cabaye MF 65 94 38 108 158 491\r\n 327 Man Utd Michael Carrick MF 59 94 38 108 133 449\r\n 631 Swansea Nathan Dyer MF 50 94 36 108 84 313\r\n 305 Man City James Milner MF 61 93 38 111 143 465\r\n 532 Southampton Adam Lallana MF 56 93 37 111 118 421\r\n 550 Stoke City Geoff Cameron DF 43 92 38 113 40 114\r\n 627 Swansea Ben Davies DF 44 92 35 113 49 156\r\n 334 Man Utd Rio Ferdinand DF 58 92 38 113 135 438\r\n 705 West Brom Chris Brunt MF 53 92 37 113 105 379\r\n 731 West Brom Jonas Olsson DF 49 92 39 113 85 293\r\n 786 Wigan Emmerson Boyce DF 47 91 38 118 73 238\r\n 338 Man Utd Javier Hernandez FW 65 90 37 119 170 491\r\n 789 Wigan Franco Di Santo FW 52 90 38 119 107 361\r\n 191 Everton Kevin Mirallas FW 66 90 36 119 173 498\r\n 658 Swansea Ashley Williams DF 49 89 36 122 94 293\r\n 657 Swansea Michel Vorm GK 51 89 37 122 104 344\r\n 686 Tottenham Hugo Lloris GK 58 89 34 122 139 438\r\n 282 Liverpool Martin Skrtel DF 56 89 38 122 134 421\r\n 761 West Ham Matthew Jarvis MF 55 89 35 122 129 409\r\n 164 Everton Victor Anichebe FW 43 88 38 127 55 114\r\n 735 West Brom Liam Ridgewell DF 48 87 38 128 97 269\r\n 754 West Ham Guy Demel DF 41 87 36 128 45 60\r\n 433 Norwich Michael Turner DF 41 86 38 130 48 60\r\n 747 West Ham Andy Carroll FW 82 86 36 130 237 548\r\n 547 Stoke City Charlie Adam MF 65 85 38 132 184 491\r\n 291 Man City Gareth Barry MF 52 85 38 132 124 361\r\n 537 Southampton Gaston Ramirez MF 52 85 34 132 124 361\r\n 302 Man City Vincent Kompany DF 70 85 38 132 202 521\r\n 383 Newcastle Jonas Gutierrez MF 55 84 39 136 142 409\r\n 341 Man Utd Shinji Kagawa MF 79 84 37 136 235 542\r\n 306 Man City Samir Nasri MF 81 83 37 138 243 546\r\n 125 Chelsea Cesar Azpilicueta DF 56 83 34 138 154 421\r\n 519 Southampton Nathaniel Clyne DF 41 83 37 138 63 60\r\n 78 Aston Villa Ashley Westwood MF 49 83 35 138 112 293\r\n 445 QPR Soares Cesar GK 47 83 35 138 100 238\r\n 241 Fulham Steve Sidwell MF 49 83 38 138 112 293\r\n 755 West Ham Mohamed Diame MF 47 83 36 138 100 238\r\n 564 Stoke City Steven Nzonzi MF 50 81 35 145 128 313\r\n 284 Liverpool Raheem Sterling MF 46 81 37 145 102 216\r\n 359 Man Utd Robin Van Persie FW 137 80 12 147 330 576\r\n 727 West Brom Youssouf Mulumbu MF 53 80 39 147 149 379\r\n 77 Aston Villa Andreas Weimann FW 51 80 31 147 136 344\r\n 782 Wigan Ali Al-Habsi GK 49 80 38 147 126 293\r\n 597 Sunderland Danny Graham FW 54 79 38 151 156 395\r\n 803 Wigan James McArthur MF 54 78 38 152 159 395\r\n 224 Fulham Alex Kacaniklic MF 43 78 38 152 95 114\r\n 591 Sunderland Carlos Cuellar DF 43 78 37 152 95 114\r\n 303 Man City Joleon Lescott DF 58 77 38 155 179 438\r\n 668 Tottenham Mousa Dembele MF 58 77 37 155 179 438\r\n 696 Tottenham Gylfi Sigurdsson MF 78 76 37 157 260 537\r\n 511 Reading Hal Robson-Kanu MF 42 76 36 157 98 82\r\n 307 Man City Matija Nastasic DF 53 76 34 157 161 379\r\n 386 Newcastle Tim Krul GK 51 75 38 160 155 344\r\n 522 Southampton Steven Davis MF 45 74 37 161 122 183\r\n 730 West Brom Peter Odemwingie FW 69 74 39 161 233 513\r\n 503 Reading Garath McCleary MF 44 73 36 163 119 156\r\n 221 Fulham Brede Hangeland DF 48 73 38 163 146 269\r\n 589 Sunderland Jack Colback MF 45 73 38 163 127 183\r\n 370 Newcastle Hatem Ben Arfa MF 73 72 38 166 252 527\r\n 392 Newcastle Davide Santon DF 47 72 39 166 141 238\r\n 415 Norwich Jonathan Howson MF 45 72 39 166 131 183\r\n 496 Reading Jimmy Kebe MF 41 72 36 166 103 60\r\n 659 Tottenham Emmanuel Adebayor FW 91 71 37 170 297 560\r\n 235 Fulham Hugo Rodallega FW 54 71 37 170 183 395\r\n 172 Everton Seamus Coleman MF 46 71 38 170 138 216\r\n 792 Wigan Maynor Figueroa DF 43 71 38 170 121 114\r\n 509 Reading Pavel Pogrebnyak FW 42 71 36 170 114 82\r\n 560 Stoke City Kenwyne Jones FW 50 70 40 175 166 313\r\n 194 Everton Steven Naismith FW 59 70 37 175 207 449\r\n 328 Man Utd Tom Cleverley MF 56 70 37 175 194 421\r\n 469 QPR Ryan Nelsen DF 41 69 38 178 116 60\r\n 259 Liverpool Phillippe Coutinho MF 71 69 13 178 261 523\r\n 481 QPR Bobby Zamora FW 61 68 39 180 226 465\r\n 546 Southampton Maya Yoshida DF 45 68 34 180 148 183\r\n 524 Southampton Jose Fonte DF 40 68 37 180 110 34\r\n 425 Norwich John Ruddy GK 44 67 38 183 145 156\r\n 360 Man Utd Nemanja Vidic DF 66 67 38 183 245 498\r\n 781 West Ham Ricardo Vaz Te FW 51 66 36 185 188 344\r\n 663 Tottenham Steven Caulker DF 44 66 37 185 151 156\r\n 337 Man Utd Ryan Giggs MF 60 65 38 187 232 458\r\n 13 Arsenal Olivier Giroud FW 77 65 18 187 281 534\r\n 255 Liverpool Jamie Carragher DF 50 65 38 187 187 313\r\n 467 QPR Stephane Mbia DF 49 65 35 187 181 293\r\n 499 Reading Mikele Leigertwood MF 45 65 36 187 159 183\r\n 462 QPR Clint Hill DF 43 64 38 192 153 114\r\n 520 Southampton Jack Cork MF 44 64 37 192 157 156\r\n 666 Tottenham Michael Dawson DF 45 64 38 192 164 183\r\n 624 Swansea Leon Britton MF 42 64 36 192 144 82\r\n 715 West Brom Zoltan Gera MF 47 64 39 192 175 238\r\n 561 Stoke City Michael Kightly MF 51 64 38 192 193 344\r\n 625 Swansea Chico DF 46 64 36 192 169 216\r\n 718 West Brom Billy Jones DF 44 63 38 199 162 156\r\n 387 Newcastle Sylvain Marveaux MF 41 62 38 200 147 60\r\n 463 QPR David Hoilett MF 56 62 38 200 229 421\r\n 556 Stoke City Matthew Etherington MF 59 61 40 202 241 449\r\n 230 Fulham Mladen Petric FW 54 61 37 202 221 395\r\n 478 QPR Armand Traore DF 48 61 38 202 191 269\r\n 636 Swansea Sung-Yeung Ki MF 60 60 34 205 246 458\r\n 544 Southampton Luke Shaw DF 40 60 37 205 151 34\r\n 779 West Ham Matthew Taylor MF 46 60 36 205 185 216\r\n 614 Sunderland Danny Rose MF 44 60 38 205 173 156\r\n 407 Norwich Mark Bunn GK 43 60 34 205 167 114\r\n 160 Chelsea John Terry DF 65 59 36 210 269 491\r\n 796 Wigan Jordi Gomez MF 52 59 38 210 220 361\r\n 488 Reading Adam Federici GK 43 59 36 210 172 114\r\n 363 Man Utd Ashley Young MF 82 58 37 213 307 548\r\n 431 Norwich Alexander Tettey MF 43 58 36 213 176 114\r\n 710 West Brom Graham Dorrans MF 50 58 39 213 213 313\r\n 695 Tottenham Raniere Sandro MF 47 58 38 213 198 238\r\n 75 Aston Villa Ron Vlaar DF 45 58 38 213 189 183\r\n 361 Man Utd Danny Welbeck FW 78 56 37 218 304 537\r\n 466 QPR Jamie Mackie FW 50 56 38 218 223 313\r\n 744 West Brom Claudio Yacob MF 49 56 37 218 218 293\r\n 516 Southampton Artur Boruc GK 45 56 30 218 196 183\r\n 297 Man City Francisco Garcia MF 50 56 34 218 223 313\r\n 559 Stoke City Cameron Jerome FW 50 55 38 223 231 313\r\n 787 Wigan Gary Caldwell DF 47 55 38 223 211 238\r\n 301 Man City Aleksandar Kolarov DF 55 55 38 223 246 409\r\n 500 Reading Adrian Mariappa DF 39 54 36 226 170 19\r\n 41 Aston Villa Gabriel Agbonlahor FW 68 54 21 226 295 508\r\n 38 Arsenal Theo Walcott MF 90 53 12 228 329 559\r\n 474 QPR Loic Remy FW 54 53 16 228 253 395\r\n 394 Newcastle Moussa Sissoko MF 54 53 15 228 253 395\r\n 274 Liverpool Leiva Lucas MF 46 53 38 228 216 216\r\n 506 Reading Sean Morrison DF 38 53 29 228 168 4\r\n 495 Reading Jem Karacan MF 42 53 36 228 192 82\r\n 153 Chelsea Victor Moses MF 62 53 35 228 277 474\r\n 249 Liverpool Joe Allen MF 45 52 37 235 214 183\r\n 406 Norwich Elliott Bennett MF 47 52 40 235 230 238\r\n 375 Newcastle Fabricio Coloccini DF 49 51 38 237 240 293\r\n 656 Swansea Gerhard Tremmel GK 41 51 38 237 197 60\r\n 470 QPR Nedum Onuoha DF 38 51 39 237 177 4\r\n 12 Arsenal Kieran Gibbs DF 53 51 15 237 262 379\r\n 26 Arsenal Lukas Podolski FW 81 50 12 241 322 546\r\n 674 Tottenham William Gallas DF 50 50 38 241 246 313\r\n 23 Arsenal Nacho Monreal DF 52 50 13 241 263 361\r\n 750 West Ham Carlton Cole FW 44 50 36 241 219 156\r\n 222 Fulham Aaron Hughes DF 40 50 38 241 194 34\r\n 772 West Ham Gary O'Neil MF 43 50 36 241 212 114\r\n 382 Newcastle Yoan Gouffran FW 62 50 15 241 290 474\r\n 477 QPR Andros Townsend MF 44 49 38 248 227 156\r\n 369 Newcastle Vurnon Anita MF 44 49 38 248 227 156\r\n 446 QPR Djibril Cisse FW 58 49 39 248 280 438\r\n 182 Everton Johnny Heitinga DF 50 49 38 248 255 313\r\n 225 Fulham Giorgos Karagounis MF 47 49 34 248 239 238\r\n 356 Man Utd Chris Smalling DF 45 48 38 253 234 183\r\n 570 Stoke City Ryan Shotton MF 46 48 38 253 238 216\r\n 319 Man City Kolo Toure DF 51 48 39 253 267 344\r\n 492 Reading Danny Guthrie MF 41 48 36 253 210 60\r\n 578 Stoke City Andy Wilkinson DF 40 48 40 253 204 34\r\n 502 Reading Alex McCarthy GK 40 48 36 253 204 34\r\n 690 Tottenham Kyle Naughton DF 39 48 37 253 199 19\r\n 810 Wigan Ivan Ramis DF 42 47 37 260 225 82\r\n 457 QPR Esteban Granero MF 52 47 36 260 270 361\r\n 180 Everton Darron Gibson MF 47 47 38 260 246 238\r\n 393 Newcastle Danny Simpson DF 46 46 38 263 246 216\r\n 440 QPR Jose Bosingwa DF 48 46 38 263 264 269\r\n 780 West Ham James Tomkins DF 41 46 36 263 222 60\r\n 579 Stoke City Marc Wilson DF 39 46 38 263 209 19\r\n 491 Reading Chris Gunter DF 38 46 36 263 203 4\r\n 240 Fulham Philippe Senderos DF 47 45 38 268 265 238\r\n 202 Fulham Chris Baird DF 39 45 38 268 215 19\r\n 288 Liverpool Andre Wisdom DF 38 45 32 268 208 4\r\n 207 Fulham Ashkan Dejagah MF 55 45 34 268 288 409\r\n 152 Chelsea Mikel MF 43 44 36 272 244 114\r\n 398 Newcastle Steven Taylor S DF 46 44 38 272 266 216\r\n 493 Reading Ian Harte DF 37 44 36 272 206 1\r\n 471 QPR Ji-Sung Park MF 52 44 38 272 279 361\r\n 479 QPR Shaun Wright-Phillip MF 48 44 39 272 268 269\r\n s\r\n\r\n 691 Tottenham Scott Parker MF 52 43 37 277 285 361\r\n 11 Arsenal Yao Gervinho MF 68 42 12 278 321 508\r\n 577 Stoke City Dean Whitehead MF 42 42 40 278 246 82\r\n 453 QPR Fabio Fabio DF 40 42 38 278 236 34\r\n 2 Arsenal Mikel Arteta MF 75 41 13 281 339 533\r\n 325 Man Utd Oliveira Anderson MF 51 41 38 281 292 344\r\n 712 West Brom Marc-Antoine Fortune FW 48 41 38 281 278 269\r\n 752 West Ham James Collins DF 46 41 14 281 274 216\r\n 195 Everton Phil Neville MF 41 40 38 285 256 60\r\n 660 Tottenham Benoit Assou-Ekotto DF 60 40 38 285 313 458\r\n 21 Arsenal Per Mertesacker DF 53 39 13 287 303 379\r\n 513 Reading Nicky Shorey DF 38 39 36 287 242 4\r\n 16 Arsenal Carl Jenkinson DF 40 39 13 287 257 34\r\n 531 Southampton Jos Hooiveld DF 40 39 37 287 257 34\r\n 436 Norwich Steven Whittaker DF 40 39 38 287 257 34\r\n 643 Swansea Luke Moore FW 43 38 36 292 275 114\r\n 399 Newcastle Cheick Tiote MF 48 38 38 292 296 269\r\n 326 Man Utd Alexander Buttner DF 50 37 36 294 302 313\r\n 458 QPR Rob Green GK 41 37 38 294 271 60\r\n 494 Reading Noel Hunt FW 46 37 36 294 291 216\r\n 678 Tottenham Tom Huddlestone MF 45 37 37 294 287 183\r\n 389 Newcastle James Perch DF 44 37 38 294 283 156\r\n 655 Swansea Dwight Tiendalli DF 45 36 32 299 293 183\r\n 69 Aston Villa Matthew Lowton DF 45 36 12 299 293 183\r\n 37 Arsenal Thomas Vermaelen DF 67 36 12 299 343 504\r\n 128 Chelsea Ryan Bertrand DF 39 35 36 302 272 19\r\n 751 West Ham Joe Cole MF 51 35 37 302 310 344\r\n 805 Wigan Callum McManaman FW 45 35 38 302 298 183\r\n 401 Newcastle Mike Williamson DF 40 35 38 302 276 34\r\n 508 Reading Alex Pearce DF 38 34 36 306 273 4\r\n 350 Man Utd Luis Nani MF 82 34 38 306 369 548\r\n 368 Newcastle Shola Ameobi FW 51 34 38 306 313 344\r\n 610 Sunderland Alfred N'Diaye MF 42 34 17 306 289 82\r\n 584 Sunderland Titus Bramble DF 40 33 38 310 286 34\r\n 311 Man City Micah Richards DF 57 33 38 310 332 429\r\n 618 Sunderland David Vaughan MF 49 33 38 310 312 293\r\n 766 West Ham George McCartney DF 38 32 36 313 282 4\r\n 528 Southampton Guly Guilherme MF 47 32 37 313 311 238\r\n 753 West Ham Jack Collison MF 46 32 36 313 309 216\r\n 464 QPR Jermaine Jenas MF 42 32 38 313 300 82\r\n 489 Reading Kaspars Gorkss DF 37 31 36 317 284 1\r\n 521 Southampton Kelvin Davis GK 41 31 37 317 301 60\r\n 19 Arsenal Vito Mannone GK 40 31 36 317 299 34\r\n 448 QPR Shaun Derry MF 42 30 38 320 306 82\r\n 764 West Ham Modibo Maiga FW 50 30 36 320 324 313\r\n 818 Wigan Ben Watson MF 50 30 38 320 324 313\r\n 402 Newcastle Mapou Yanga-Mbiwa DF 49 29 15 323 328 293\r\n 737 West Brom Markus Rosenberg FW 59 29 37 323 357 449\r\n 355 Man Utd Paul Scholes MF 50 29 38 323 331 313\r\n 426 Norwich Ryan Ryan Bennett DF 39 28 38 326 304 19\r\n 526 Southampton Daniel Fox DF 40 28 37 326 308 34\r\n 51 Aston Villa Ciaran Clark DF 44 28 12 326 318 156\r\n 290 Man City Mario Balotelli FW 86 28 38 326 389 554\r\n 454 QPR Alejandro Faurlin MF 47 28 38 326 326 238\r\n 304 Man City Sisenando Maicon DF 62 28 34 326 363 474\r\n 45 Aston Villa Joe Bennett DF 44 28 36 326 318 156\r\n 791 Wigan Roger Espinoza MF 41 27 16 333 315 60\r\n 44 Aston Villa Barry Bannan MF 47 27 12 333 333 238\r\n 651 Swansea Itay Shechter FW 50 27 35 333 342 313\r\n 46 Aston Villa Darren Bent FW 78 27 18 333 384 537\r\n 280 Liverpool Nuri Sahin MF 54 27 35 333 352 395\r\n 27 Arsenal Aaron Ramsey MF 54 27 12 333 352 395\r\n 231 Fulham Kieran Richardson MF 53 27 36 333 351 379\r\n 527 Southampton Paulo Gazzaniga GK 40 26 37 340 316 34\r\n 497 Reading Stephen Kelly DF 40 26 38 340 316 34\r\n 783 Wigan Antolin Alcaraz DF 42 26 38 340 320 82\r\n 340 Man Utd Phil Jones DF 57 26 38 340 362 429\r\n 421 Norwich Steve Morison FW 49 26 38 340 345 293\r\n 346 Man Utd Anders Lindegaard GK 51 26 38 340 350 344\r\n 312 Man City Jack Rodwell MF 46 26 37 340 336 216\r\n 388 Newcastle Gabriel Obertan MF 41 25 39 347 323 60\r\n 728 West Brom Boaz Myhill GK 44 25 39 347 334 156\r\n 582 Sunderland Phil Bardsley DF 44 25 37 347 334 156\r\n 56 Aston Villa Karim El Ahmadi MF 42 25 16 347 327 82\r\n 798 Wigan David Jones MF 43 24 39 351 337 114\r\n 514 Reading Jay Tabb MF 43 24 36 351 337 114\r\n 269 Liverpool Brad Jones GK 44 24 37 351 340 156\r\n 62 Aston Villa Brett Holman MF 55 24 12 351 364 409\r\n 482 Reading Hope Akpan MF 45 24 17 351 344 183\r\n 376 Newcastle Mathieu Debuchy DF 47 24 17 351 348 238\r\n 416 Norwich Simeon Jackson FW 47 24 38 351 348 238\r\n 449 QPR Samba Diakite MF 44 24 39 351 340 156\r\n 672 Tottenham Brad Friedel GK 48 23 37 359 360 269\r\n 642 Swansea Garry Monk DF 42 22 36 360 346 82\r\n 5 Arsenal Alex Chamberlain MF 69 22 13 360 391 513\r\n 621 Swansea Kemy Agustien MF 45 22 36 360 358 183\r\n 545 Southampton James Ward-Prowse MF 43 22 37 360 347 114\r\n 371 Newcastle Gael Bigirimana MF 43 21 38 364 359 114\r\n 281 Liverpool Jonjo Shelvey MF 51 21 39 364 371 344\r\n 212 Fulham Urby Emanuelson MF 46 21 13 364 361 216\r\n 377 Newcastle Rob Elliot GK 40 20 38 367 352 34\r\n 734 West Brom Steven Reid MF 47 20 39 367 367 238\r\n 812 Wigan Joel Robles GK 40 20 15 367 352 34\r\n 815 Wigan Ronnie Stam DF 38 19 38 370 352 4\r\n 17 Arsenal Laurent Koscielny DF 53 19 12 370 382 379\r\n 64 Aston Villa Stephen Ireland MF 50 19 12 370 377 313\r\n 733 West Brom Goran Popov DF 44 19 34 370 366 156\r\n 510 Reading Jason Roberts FW 45 18 36 374 372 183\r\n 263 Liverpool Fernandez Saez FW 47 18 33 374 375 238\r\n 254 Liverpool Fabio Borini FW 72 18 37 374 409 526\r\n 315 Man City Scott Sinclair MF 60 18 37 374 392 458\r\n 197 Everton Bryan Oviedo MF 48 18 34 374 379 269\r\n 455 QPR Anton Ferdinand DF 41 17 39 379 369 60\r\n 67 Aston Villa Eric Lichaj DF 43 17 12 379 373 114\r\n 588 Sunderland Lee Cattermole MF 43 17 38 379 373 114\r\n 654 Swansea Neil Taylor DF 45 17 36 379 378 183\r\n 677 Tottenham Lewis Holtby MF 63 17 14 379 401 482\r\n 586 Sunderland Fraizer Campbell FW 49 17 37 379 383 293\r\n 742 West Brom Jerome Thomas MF 51 17 39 379 386 344\r\n 7 Arsenal Vassiriki Diaby MF 61 17 12 379 398 465\r\n 127 Chelsea Yossi Benayoun MF 61 17 36 379 398 465\r\n 29 Arsenal Bacary Sagna DF 47 17 15 379 381 238\r\n 404 Norwich Leon Barnett DF 37 16 38 389 365 1\r\n 210 Fulham Mahamadou Diarra MF 47 16 37 389 385 238\r\n 74 Aston Villa Yacouba Sylla MF 42 16 14 389 376 82\r\n 599 Sunderland Matthew Kilgallon DF 38 16 37 389 368 4\r\n 685 Tottenham Jake Livermore MF 41 15 39 393 380 60\r\n 209 Fulham Clint Dempsey MF 92 15 1 393 436 562\r\n 385 Newcastle Steve Harper GK 45 15 38 393 386 183\r\n 228 Fulham Stanislav Manolev DF 42 14 13 396 386 82\r\n 378 Newcastle Shane Ferguson MF 43 14 38 396 389 114\r\n 183 Everton Tony Hibbert DF 50 14 38 396 396 313\r\n 535 Southampton Emmanuel Mayuka FW 48 14 35 396 394 269\r\n 441 QPR Jay Bothroyd FW 47 14 40 396 393 238\r\n 48 Aston Villa Jordan Bowery FW 45 13 36 401 395 183\r\n 330 Man Utd Jonathan Evans J DF 48 13 1 401 400 269\r\n 620 Sunderland Connor Wickham FW 50 13 37 401 405 313\r\n 213 Fulham Eyong Enoh MF 50 13 13 401 405 313\r\n 31 Arsenal Clarindo Santos DF 49 13 14 401 403 293\r\n 192 Everton Jan Mucha GK 43 12 38 406 397 114\r\n 217 Fulham Emmanuel Frimpong MF 45 12 15 406 402 183\r\n 103 Bolton Mark Davies M MF 48 12 2 406 409 269\r\n 148 Chelsea Marko Marin MF 66 12 35 406 429 498\r\n 184 Everton Thomas Hitzlsperger MF 50 12 30 406 412 313\r\n 335 Man Utd Darren Fletcher MF 54 12 38 406 416 395\r\n 565 Stoke City Michael Owen FW 50 12 35 406 412 313\r\n 740 West Brom Gabriel Tamas DF 42 11 39 413 404 82\r\n 391 Newcastle Sammy Sammy Ameobi FW 43 11 39 413 408 114\r\n 72 Aston Villa Charles N'Zogbia MF 66 11 13 413 434 498\r\n 114 Bolton Martin Petrov MF 52 11 2 413 419 361\r\n 88 Blackburn David Hoilett FW 55 11 3 413 423 409\r\n 475 QPR Tommy Smith FW 45 11 40 413 411 183\r\n 43 Aston Villa Nathan Baker DF 39 10 12 419 407 19\r\n 662 Tottenham Tom Carroll MF 42 10 37 419 414 82\r\n 39 Arsenal Jack Wilshere MF 63 10 12 419 441 482\r\n 35 Arsenal Wojciech Szczesny GK 53 10 12 419 427 379\r\n 85 Blackburn Morten Gamst Gamst P MF 62 10 2 419 439 474\r\n edersen\r\n\r\n 615 Sunderland Louis Saha FW 49 10 37 419 422 293\r\n 205 Fulham Matthew Briggs DF 39 9 38 425 415 19\r\n 158 Chelsea Oriol Romeu MF 41 9 37 425 417 60\r\n 574 Stoke City Matthew Upson DF 41 9 39 425 417 60\r\n 216 Fulham Kerim Frei MF 43 9 37 425 420 114\r\n 613 Sunderland Kieran Richardson MF 58 9 1 425 444 438\r\n 585 Sunderland Wes Brown DF 46 9 38 425 424 216\r\n 201 Everton Apostolos Vellios FW 47 9 38 425 425 238\r\n 223 Fulham Andrew Johnson A FW 47 9 1 425 425 238\r\n 257 Liverpool Sebastian Coates DF 44 9 39 425 421 156\r\n 450 QPR Kieron Dyer MF 44 8 39 434 429 156\r\n 785 Wigan Mauro Boselli FW 50 8 37 434 440 313\r\n 54 Aston Villa Fabian Delph MF 46 8 12 434 432 216\r\n 486 Reading Shaun Cummings DF 38 7 36 437 428 4\r\n 273 Liverpool Dirk Kuyt MF 94 7 1 437 478 567\r\n 166 Everton Ross Barkley MF 41 7 39 437 433 60\r\n 797 Wigan Angelo Henriquez FW 42 7 16 437 434 82\r\n 743 West Brom George Thorne MF 43 7 39 437 437 114\r\n 430 Norwich Andrew Surman MF 43 7 38 437 437 114\r\n 580 Stoke City Jonathan Woodgate DF 45 7 2 437 442 183\r\n 352 Man Utd Nick Powell MF 45 7 37 437 442 183\r\n 465 QPR Andrew Johnson FW 46 7 38 437 446 216\r\n 6 Arsenal Francis Coquelin MF 47 7 13 437 448 238\r\n 82 Blackburn Scott Dann DF 47 7 1 437 448 238\r\n 272 Liverpool Martin Kelly DF 51 7 38 437 452 344\r\n 42 Aston Villa Marc Albrighton MF 52 7 12 437 453 361\r\n 109 Bolton Ivan Klasnic FW 59 7 2 437 456 449\r\n 515 Reading Stuart Taylor GK 40 7 35 437 431 34\r\n 162 Chelsea Ross Turnbull GK 39 6 36 452 445 19\r\n 409 Norwich Lee Camp GK 40 6 15 452 447 34\r\n 310 Man City Karim Rekik DF 43 6 38 452 450 114\r\n 1 Arsenal Andrey Arshavin MF 65 6 12 452 470 491\r\n 637 Swansea Roland Lamah MF 50 6 14 452 455 313\r\n 229 Fulham Danny Murphy MF 61 6 1 452 464 465\r\n 9 Arsenal Lukasz Fabianski GK 43 6 12 452 450 114\r\n 539 Southampton Frazer Richardson DF 41 5 37 459 454 60\r\n 680 Tottenham Harry Kane FW 43 5 38 459 457 114\r\n 151 Chelsea Raul Meireles MF 63 5 36 459 474 482\r\n 84 Blackburn Mauro Formica MF 49 5 2 459 462 293\r\n 244 Fulham David Stockdale GK 43 5 38 459 457 114\r\n 709 West Brom Craig Dawson DF 38 4 39 464 459 4\r\n 439 QPR Tal Ben Haim DF 39 4 17 464 460 19\r\n 801 Wigan Adrian Lopez DF 39 4 38 464 460 19\r\n 777 West Ham Jordan Spence DF 40 4 29 464 463 34\r\n 566 Stoke City Wilson Palacios MF 41 4 39 464 465 60\r\n 52 Aston Villa Simon Dawkins MF 42 4 14 464 466 82\r\n 699 Tottenham Rafael Van der Vaart MF 89 4 37 464 509 557\r\n 717 West Brom Gonzalo Jara DF 43 4 39 464 468 114\r\n 61 Aston Villa Chris Herd MF 43 4 12 464 468 114\r\n 294 Man City Nigel De Jong MF 44 4 38 464 471 156\r\n 58 Aston Villa Shay Given GK 45 4 12 464 472 183\r\n 107 Bolton Jussi Jaaskelainen GK 48 4 2 464 473 269\r\n 251 Liverpool Oussama Assaidi MF 57 4 36 464 483 429\r\n 110 Bolton Zat Knight DF 42 4 2 464 466 82\r\n 538 Southampton Ben Reeves DF 38 3 37 478 475 4\r\n 567 Stoke City Jermaine Pennant MF 50 3 38 478 491 313\r\n 122 Chelsea Nathan Ake DF 40 3 20 478 477 34\r\n 384 Newcastle Massadio Haidara DF 41 3 15 478 479 60\r\n 608 Sunderland David Meyler MF 42 3 38 478 480 82\r\n 140 Chelsea Henrique Hilario GK 42 3 38 478 480 82\r\n 518 Southampton Richard Chaplow MF 42 3 37 478 480 82\r\n 309 Man City Abdul Razak MF 43 3 39 478 484 114\r\n 806 Wigan Ryo Miyaichi MF 43 3 12 478 484 114\r\n 774 West Ham Emanuel Pogatetz DF 43 3 14 478 484 114\r\n 373 Newcastle Adam Campbell FW 45 3 20 478 487 183\r\n 756 West Ham Alou Diarra MF 45 3 36 478 487 183\r\n 381 Newcastle Dan Gosling MF 46 3 38 478 489 216\r\n 181 Everton Magaye Gueye FW 46 3 38 478 489 216\r\n 568 Stoke City Danny Pugh MF 50 3 2 478 491 313\r\n 607 Sunderland James McFadden FW 50 3 28 478 491 313\r\n 487 Reading Daniel Daniel Carric DF 38 3 17 478 475 4\r\n o\r\n\r\n 653 Swansea Alan Tate DF 38 2 36 495 494 4\r\n 321 Man City Gnegneri Yaya Toure MF 77 2 1 495 530 534\r\n 459 QPR Michael Harriman DF 39 2 38 495 496 19\r\n 795 Wigan Roman Golobart DF 40 2 24 495 497 34\r\n 605 Sunderland Kader Mangane DF 40 2 16 495 497 34\r\n 400 Newcastle Haris Vuckic MF 42 2 40 495 499 82\r\n 119 Bolton Gretar Rafn Steinsso DF 42 2 2 495 499 82\r\n n\r\n\r\n 155 Chelsea Lucas Piazon MF 42 2 35 495 499 82\r\n 226 Fulham Pajtim Kasami MF 42 2 38 495 499 82\r\n 523 Southampton Steve De Ridder MF 42 2 37 495 499 82\r\n 411 Norwich David Fox MF 43 2 38 495 504 114\r\n 118 Bolton Paul Robinson DF 43 2 2 495 504 114\r\n 116 Bolton Nigel Reo-Coker MF 44 2 1 495 506 156\r\n 833 Wolves Karl Henry MF 44 2 1 495 506 156\r\n 113 Bolton Fabrice Muamba MF 44 2 1 495 506 156\r\n 707 West Brom Simon Cox FW 45 2 38 495 510 183\r\n 390 Newcastle Nile Ranger MF 45 2 26 495 510 183\r\n 832 Wolves Wayne Hennessey GK 46 2 1 495 512 216\r\n 593 Sunderland Ahmed Elmohamady MF 49 2 38 495 513 293\r\n 543 Southampton Billy Sharp FW 49 2 37 495 513 293\r\n 634 Swansea Danny Graham FW 50 2 1 495 515 313\r\n 679 Tottenham Younes Kaboul DF 50 2 38 495 515 313\r\n 91 Blackburn Marcus Marcus Olsson MF 50 2 1 495 515 313\r\n 738 West Brom Paul Scharner MF 51 2 2 495 518 344\r\n 115 Bolton Darren Pratley MF 52 2 2 495 519 361\r\n 208 Fulham Moussa Dembele FW 52 2 1 495 519 361\r\n 95 Blackburn Jason Roberts FW 53 2 3 495 521 379\r\n 283 Liverpool Jay Spearing MF 54 2 38 495 522 395\r\n 175 Everton Royston Drenthe MF 54 2 1 495 522 395\r\n 102 Bolton Kevin Davies K FW 57 2 2 495 524 429\r\n 835 Wolves Matthew Jarvis MF 57 2 1 495 524 429\r\n 682 Tottenham Niko Kranjcar MF 60 2 1 495 526 458\r\n 83 Blackburn David Dunn MF 62 2 3 495 527 474\r\n 157 Chelsea Ramires MF 69 2 1 495 528 513\r\n 694 Tottenham Louis Saha FW 69 2 1 495 528 513\r\n 775 West Ham Daniel Potts DF 38 2 36 495 494 4\r\n 396 Newcastle James Tavernier DF 39 1 38 531 531 19\r\n 136 Chelsea Didier Drogba FW 101 1 1 531 576 570\r\n 73 Aston Villa Enda Stevens DF 39 1 12 531 531 19\r\n 138 Chelsea Paulo Ferreira DF 40 1 36 531 534 34\r\n 242 Fulham Alex Smith DF 40 1 34 531 534 34\r\n 227 Fulham Stephen Kelly DF 40 1 1 531 534 34\r\n 333 Man Utd Fabio Fabio DF 42 1 1 531 537 82\r\n 793 Wigan Fraser Fyvie MF 42 1 37 531 537 82\r\n 176 Everton Shane Duffy DF 42 1 38 531 537 82\r\n 57 Aston Villa Gary Gardner MF 42 1 13 531 537 82\r\n 14 Arsenal Serge Gnabry MF 43 1 29 531 541 114\r\n 443 QPR DJ Campbell FW 43 1 40 531 541 114\r\n 555 Stoke City Maurice Edu MF 43 1 36 531 541 114\r\n 848 Wolves Stephen Ward DF 43 1 1 531 541 114\r\n 820 Wolves Christophe Berra DF 43 1 1 531 541 114\r\n 846 Wolves Richard Stearman DF 43 1 1 531 541 114\r\n 758 West Ham Robert Hall FW 43 1 34 531 541 114\r\n 512 Reading Dominic Samuel FW 44 1 23 531 548 156\r\n 419 Norwich Chris Martin C FW 44 1 38 531 548 156\r\n 814 Wigan Conor Sammon FW 45 1 38 531 550 183\r\n 633 Swansea Mark Gower MF 45 1 36 531 550 183\r\n 553 Stoke City Rory Delap MF 45 1 40 531 550 183\r\n 837 Wolves Eggert Jonsson MF 45 1 1 531 550 183\r\n 206 Fulham Simon Davies MF 46 1 38 531 554 216\r\n 670 Tottenham Yago Falque MF 46 1 37 531 554 216\r\n 96 Blackburn Ruben Rochina FW 47 1 3 531 556 238\r\n 790 Wigan Mohamed Diame MF 48 1 1 531 557 269\r\n 397 Newcastle Ryan Taylor R DF 48 1 38 531 557 269\r\n 583 Sunderland Phillip Bardsley DF 48 1 1 531 557 269\r\n 741 West Brom Somen Tchoyi MF 48 1 2 531 557 269\r\n 825 Wolves David Edwards MF 49 1 1 531 561 293\r\n 53 Aston Villa Nathan Delfouneso FW 50 1 21 531 562 313\r\n 841 Wolves Nenad Milijas MF 52 1 1 531 563 361\r\n 827 Wolves Steven Fletcher FW 52 1 1 531 563 361\r\n 839 Wolves Michael Kightly MF 54 1 1 531 565 395\r\n 130 Chelsea Jose Bosingwa DF 55 1 1 531 566 409\r\n 86 Blackburn David Goodwillie FW 55 1 2 531 566 409\r\n 342 Man Utd Will Keane FW 55 1 2 531 566 409\r\n 823 Wolves Kevin Doyle FW 57 1 1 531 569 429\r\n 137 Chelsea Michael Essien MF 63 1 36 531 570 482\r\n 171 Everton Tim Cahill MF 65 1 38 531 571 491\r\n 692 Tottenham Roman Pavlyuchenko FW 70 1 1 531 572 521\r\n 146 Chelsea Romelu Lukaku FW 74 1 3 531 573 530\r\n 247 Liverpool Charlie Adam MF 86 1 1 531 574 554\r\n 256 Liverpool Andy Carroll FW 91 1 1 531 575 560\r\n 98 Bolton Marcos Alonso DF 39 1 1 531 531 19\r\n\r\n576 rows selected.\r\n<\/pre>\n<\/div>\nSQL Solution with Recursive Subquery Factoring<\/strong><\/p>\nSQL<\/em><\/p>\nNote that currently I have retained the fantasy league table and column names, but they could as well be the generic items and categories in place of players and teams: This is a generic solution.<\/p>\n
\n
\r\nVAR KEEP_NUM NUMBER\r\nVAR MAX_PRICE NUMBER\r\nBEGIN\r\n :KEEP_NUM := 40;\r\n :MAX_PRICE := 900;\r\nEND;\r\n\/\r\nPROMPT Top ten solutions\r\nWITH position_counts AS (\r\nSELECT Max (CASE id WHEN 'AL' THEN min_players END) team_size\r\n FROM positions\r\n), pos_runs AS (\r\nSELECT id, Sum (CASE WHEN id != 'AL' THEN min_players END) OVER (ORDER BY id DESC) num_remain, min_players, max_players\r\n FROM positions\r\n), players_ranked AS (\r\nSELECT id,\r\n position_id,\r\n price,\r\n avg_points,\r\n appearances,\r\n Row_Number() OVER (ORDER BY position_id, avg_points DESC) rnk,\r\n Min (price) OVER () min_price\r\n FROM players\r\n), rsf (path_rnk, nxt_id, lev, tot_price, tot_profit, pos_id, n_pos, team_size, min_players, pos_path, path) AS (\r\nSELECT 0, 0, 0, 0, 0, 'AL', 0, c.team_size, 0, CAST (NULL AS VARCHAR2(400)) pos_path, CAST (NULL AS VARCHAR2(400)) path\r\n FROM position_counts c\r\n UNION ALL\r\nSELECT Row_Number() OVER (PARTITION BY r.pos_path || p.position_id ORDER BY r.tot_profit + p.avg_points DESC),\r\n p.rnk,\r\n r.lev + 1,\r\n r.tot_price + p.price,\r\n r.tot_profit + p.avg_points,\r\n p.position_id,\r\n CASE p.position_id WHEN r.pos_id THEN r.n_pos + 1 ELSE 1 END,\r\n r.team_size,\r\n m1.min_players,\r\n r.pos_path || p.position_id,\r\n r.path || LPad (p.id, 3, '0')\r\n FROM rsf r\r\n JOIN players_ranked p\r\n ON p.rnk > r.nxt_id\r\n JOIN pos_runs m1\r\n ON m1.id = p.position_id\r\n AND CASE p.position_id WHEN r.pos_id THEN r.n_pos + 1 ELSE 1 END <= m1.max_players\r\n AND r.team_size - r.lev - 1 >= m1.num_remain - CASE p.position_id WHEN r.pos_id THEN r.n_pos + 1 ELSE 1 END\r\n AND (r.lev = 0 OR p.position_id = r.pos_id OR r.n_pos >= r.min_players)\r\n WHERE r.tot_price + p.price + (r.team_size - r.lev - 1) * p.min_price <= :MAX_PRICE\r\n AND r.path_rnk < :KEEP_NUM\r\n AND r.lev < r.team_size\r\n), paths_ranked AS (\r\nSELECT tot_price,\r\n tot_profit,\r\n team_size,\r\n Row_Number () OVER (ORDER BY tot_profit DESC, tot_price) r_profit,\r\n path\r\n FROM rsf\r\n WHERE lev = team_size\r\n), top_ten_paths AS (\r\nSELECT tot_price,\r\n tot_profit,\r\n r_profit,\r\n path,\r\n player_index\r\n FROM paths_ranked\r\n CROSS JOIN (SELECT LEVEL player_index FROM position_counts CONNECT BY LEVEL <= team_size)\r\n WHERE r_profit <= 10\r\n), top_ten_teams AS (\r\nSELECT tot_price,\r\n tot_profit,\r\n r_profit,\r\n path,\r\n player_index,\r\n Substr (path, (player_index - 1) * 3 + 1, 3) player_id\r\n FROM top_ten_paths\r\n)\r\nSELECT t.tot_profit,\r\n t.tot_price,\r\n t.r_profit rnk,\r\n p.position_id,\r\n t.player_id p_id,\r\n p.player_name,\r\n p.club_name,\r\n p.price,\r\n p.avg_points\r\n FROM top_ten_teams t\r\n JOIN players p\r\n ON p.id = t.player_id\r\nORDER BY t.tot_profit DESC, t.tot_price, t.path, p.position_id, t.player_index<\/pre>\n<\/div>\nHow It Works<\/em><\/p>\nThe solution approach is based on the method used to provide exact solutions for knapsack problems in my earlier article, but with a number of extensions to cater for the new category constraints, and to reduce searching to manageable proportions.<\/p>\n
\n- position_counts subquery: Gets the team size<\/li>\n
- pos_runs subquery: Computes the running sums of the item category minima going backwards by category id<\/li>\n
- players_ranked subquery: Computes a unique rank for the items, ordered by category, then profit descending<\/li>\n
- rsf subquery: A recursive subquery that returns a set of item sets in the form of strings of the concatenated item ids<\/li>\n
- rsf anchor branch: Initialises the recursion with a single record<\/li>\n
- rsf recursive branch: Items are joined having strictly higher rank, and such that the constraints are not violated, both at the current position and with any possible extrapolations\n
- Row_Number is used to rank the records by overall profit, and the where clause excludes records from the previous iteration that have rank below an input figure;
\nthis exclusion is what makes the computation practical; the ranking is partitioned by the category path, which is important to avoid closing off solution paths too early<\/li>\n - Item category minima are treated differently from the maxima; once a category is in a position, the subsequent positions are required to be of the same category until the minimum number is reached<\/li>\n
- paths_ranked subquery: Excludes records that are not of full length,, and ranks those that are by profit<\/li>\n
- top_ten_paths subquery: Selects the top ten paths and cross-joins them with a row-generator to provide an indexed set of records with set size cardinality for each path<\/li>\n
- top_ten_teams subquery: Builds the item records for each of the best sets by extracting the item id from the paths according to index<\/li>\n
- Main query: Joins items table to provide additional attributes<\/li>\n<\/ul>\n
PL\/SQL Recursive Solution<\/strong><\/p>\nThis is a version in the form of a pipelined function.<\/p>\n
SQL<\/em><\/p>\n\r\nSELECT t.sol_profit, \r\n t.sol_price,\r\n Dense_Rank() OVER (ORDER BY t.sol_profit DESC, t.sol_price) RNK,\r\n p.position_id,\r\n t.item_id, \r\n p.club_name,\r\n p.player_name,\r\n p.price,\r\n p.avg_points\r\n FROM TABLE (Item_Cats.Best_N_Sets (\r\n p_keep_size => 10, \r\n p_max_calls => 100000,\r\n p_n_size => 10, \r\n p_max_price => 900,\r\n p_cat_cur => CURSOR (\r\n SELECT id, min_players, max_players\r\n FROM positions\r\n ORDER BY CASE WHEN id != 'AL' THEN 0 END, id\r\n ), \r\n p_item_cur => CURSOR (\r\n SELECT id, price, avg_points, position_id\r\n FROM players\r\n ORDER BY position_id, avg_points DESC\r\n )\r\n )\r\n ) t\r\n JOIN players p\r\n ON p.id = t.item_id\r\n ORDER BY t.sol_profit DESC, t.sol_price, p.position_id, t.item_id\r\n<\/pre>\nPackage<\/em><\/p>\n\n
\r\nCREATE OR REPLACE PACKAGE Item_Cats AS\r\n\/**************************************************************************************************\r\n\r\nAuthor: Brendan Furey\r\nDate: 7 July 2013\r\nDescription: Brendan's pipelined function solution for the knapsack problem with one container,\r\n and items having categories with validity bands, as described at\r\n http:\/\/aprogrammerwrites.eu\/?p=878 (SQL for the Fantasy Football Knapsack Problem)\r\n\r\n***************************************************************************************************\/\r\nTYPE sol_detail_rec_type IS RECORD (\r\n set_id NUMBER,\r\n item_id VARCHAR2(100),\r\n sol_price NUMBER,\r\n sol_profit NUMBER\r\n );\r\nTYPE sol_detail_list_type IS VARRAY(100) OF sol_detail_rec_type;\r\n\r\nFUNCTION Best_N_Sets ( p_keep_size PLS_INTEGER, \r\n p_max_calls PLS_INTEGER, \r\n p_n_size PLS_INTEGER, \r\n p_max_price PLS_INTEGER, \r\n p_cat_cur SYS_REFCURSOR, \r\n p_item_cur SYS_REFCURSOR) RETURN sol_detail_list_type PIPELINED;\r\n\r\nEND Item_Cats;\r\n\/\r\nSHO ERR\r\n\r\nCREATE OR REPLACE PACKAGE BODY Item_Cats AS\r\n\r\nc_cat_all CONSTANT VARCHAR2(3) := 'AL';\r\nc_hash_renew_point CONSTANT PLS_INTEGER := 1000;\r\n--\r\n-- Bulk collect array types\r\n--\r\nTYPE cat_rec_type IS RECORD (\r\n id VARCHAR2(3),\r\n min_items PLS_INTEGER,\r\n max_items PLS_INTEGER\r\n );\r\nTYPE cat_list_type IS VARRAY(100) OF cat_rec_type;\r\n\r\nTYPE item_cat_rec_type IS RECORD (\r\n id VARCHAR2(10),\r\n price PLS_INTEGER,\r\n profit PLS_INTEGER,\r\n cat_id VARCHAR2(3)\r\n );\r\nTYPE item_cat_list_type IS VARRAY(1000) OF item_cat_rec_type;\r\n\r\nTYPE chr_hash_type IS TABLE OF PLS_INTEGER INDEX BY VARCHAR2(30);\r\n--\r\n-- Input data LOL types\r\n--\r\nTYPE num_range_rec_type IS RECORD (\r\n item_beg PLS_INTEGER,\r\n item_end PLS_INTEGER\r\n );\r\nTYPE num_range_list_type IS VARRAY(1000) OF num_range_rec_type;\r\nTYPE num_list_type IS VARRAY(100) OF PLS_INTEGER;\r\n--\r\n-- Solution types\r\n--\r\nTYPE id_list_type IS VARRAY(100) OF VARCHAR2(10);\r\nTYPE sol_rec_type IS RECORD ( -- trial solution and record in retained array\r\n item_list id_list_type,\r\n price PLS_INTEGER,\r\n profit PLS_INTEGER\r\n );\r\nTYPE sol_list_type IS VARRAY(100) OF sol_rec_type; -- retained solutions\r\n\r\nTYPE int_hash_type IS TABLE OF PLS_INTEGER INDEX BY PLS_INTEGER;\r\n\r\ng_keep_size PLS_INTEGER;\r\ng_max_calls PLS_INTEGER;\r\ng_n_size PLS_INTEGER;\r\ng_max_price PLS_INTEGER;\r\n\r\ng_cat_hash chr_hash_type;\r\ng_item_range_list num_range_list_type := num_range_list_type();\r\ng_hash_buffer int_hash_type;\r\ng_profit_hash int_hash_type;\r\ng_trial_sol sol_rec_type;\r\ng_sol_list sol_list_type := sol_list_type();\r\ng_cat_list cat_list_type;\r\ng_item_cat_list item_cat_list_type;\r\n\r\ng_n_cats PLS_INTEGER;\r\ng_n_items PLS_INTEGER;\r\ng_set_size PLS_INTEGER;\r\ng_nth_profit PLS_INTEGER := 0;\r\ng_min_item_price PLS_INTEGER := 1000000;\r\ng_max_item_profit PLS_INTEGER := 0;\r\ng_min_price_togo num_list_type := num_list_type();\r\ng_max_profit_togo num_list_type := num_list_type();\r\ng_n_recursive_calls PLS_INTEGER := 0;\r\ng_n_sols PLS_INTEGER := 0;\r\n\r\nPROCEDURE Write_Log (p_line VARCHAR2, p_debug_level PLS_INTEGER DEFAULT 0) IS\r\nBEGIN\r\n\r\n IF Utils.g_debug_level >= p_debug_level THEN\r\n Utils.Write_Log (p_line);\r\n END IF;\r\n\r\nEND Write_Log;\r\n\r\nFUNCTION Dedup_Hash (p_card PLS_INTEGER, p_key PLS_INTEGER, p_hash int_hash_type) RETURN PLS_INTEGER IS\r\n l_trial_key PLS_INTEGER := p_card * p_key;\r\nBEGIN\r\n\r\n LOOP\r\n\r\n IF p_hash.EXISTS (l_trial_key) THEN\r\n l_trial_key := l_trial_key + 1;\r\n ELSE\r\n EXIT;\r\n END IF;\r\n\r\n END LOOP;\r\n RETURN l_trial_key;\r\n\r\nEND Dedup_Hash;\r\n\r\nPROCEDURE Pop_Arrays (p_cat_cur SYS_REFCURSOR, p_item_cur SYS_REFCURSOR) IS\r\n n_cat PLS_INTEGER := 0;\r\n l_price PLS_INTEGER;\r\n l_profit PLS_INTEGER;\r\n\r\n l_last_cat VARCHAR2(30) := '???';\r\n\r\n l_item_price_hash int_hash_type;\r\n l_item_profit_hash int_hash_type;\r\n\r\nBEGIN\r\n\r\n FETCH p_cat_cur BULK COLLECT INTO g_cat_list;\r\n CLOSE p_cat_cur;\r\n Write_Log ('Collected ' || g_cat_list.COUNT || ' cats');\r\n\r\n FETCH p_item_cur BULK COLLECT INTO g_item_cat_list;\r\n CLOSE p_item_cur;\r\n Write_Log ('Collected ' || g_item_cat_list.COUNT || ' items');\r\n\r\n\r\n Write_Log (g_n_cats || ' cats');\r\n\r\n g_n_cats := g_cat_list.COUNT - 1;\r\n g_item_range_list.EXTEND (g_n_cats);\r\n FOR i IN 1..g_cat_list.COUNT LOOP\r\n\r\n IF g_cat_list(i).id = c_cat_all THEN\r\n g_set_size := g_cat_list(i).min_items;\r\n ELSE\r\n g_cat_hash (g_cat_list(i).id) := i;\r\n END IF;\r\n\r\n END LOOP;\r\n g_cat_list.TRIM;\r\n\r\n FOR i IN 1..g_item_cat_list.COUNT LOOP\r\n\r\n IF g_item_cat_list(i).price < g_min_item_price THEN\r\n g_min_item_price := g_item_cat_list(i).price;\r\n END IF;\r\n\r\n IF g_item_cat_list(i).profit > g_max_item_profit THEN\r\n g_max_item_profit := g_item_cat_list(i).profit;\r\n END IF;\r\n l_item_price_hash (Dedup_Hash (p_card => g_item_cat_list.COUNT, p_key => g_item_cat_list(i).price, p_hash => l_item_price_hash)) := i;\r\n l_item_profit_hash (Dedup_Hash (p_card => g_item_cat_list.COUNT, p_key => g_item_cat_list(i).profit, p_hash => l_item_profit_hash)) := i;\r\n\r\n IF g_item_cat_list(i).cat_id != l_last_cat THEN\r\n--\r\n-- Cat has changed, so reset the itm number to zero, and assign the list of items \r\n-- for previous cat\r\n--\r\n n_cat := n_cat + 1;\r\n g_item_range_list (n_cat).item_beg := i;\r\n IF i > 1 THEN\r\n g_item_range_list (n_cat - 1).item_end := i - 1;\r\n END IF;\r\n l_last_cat := g_item_cat_list(i).cat_id;\r\n\r\n END IF;\r\n\r\n END LOOP;\r\n\r\n g_n_items := g_item_cat_list.COUNT;\r\n g_item_range_list (g_n_cats).item_end := g_n_items;\r\n g_min_price_togo.EXTEND (g_set_size);\r\n g_max_profit_togo.EXTEND (g_set_size);\r\n l_price := l_item_price_hash.FIRST;\r\n l_profit := l_item_profit_hash.LAST;\r\n Write_Log ('Hash first price min \/ profit max ' || l_price || ' \/ ' || l_profit);\r\n g_min_price_togo (g_set_size) := 0;\r\n g_max_profit_togo (g_set_size) := 0;\r\n\r\n FOR i IN 1..g_set_size - 1 LOOP\r\n\r\n g_min_price_togo (g_set_size - i) := g_min_price_togo (g_set_size - i + 1) + l_price \/ g_item_cat_list.COUNT;\r\n g_max_profit_togo (g_set_size - i) := g_max_profit_togo (g_set_size - i + 1) + l_profit \/ g_item_cat_list.COUNT;\r\n\r\n l_price := l_item_price_hash.NEXT (l_price);\r\n l_profit := l_item_profit_hash.PRIOR (l_profit);\r\n Write_Log ((g_set_size - i) || ': price min \/ profit max ' || g_min_price_togo (g_set_size - i) || ' \/ ' || g_max_profit_togo (g_set_size - i));\r\n\r\n END LOOP;\r\n\r\n Write_Log ('Price min \/ profit max ' || g_min_item_price || ' \/ ' || g_max_item_profit);\r\n FOR i IN 1..g_n_cats LOOP\r\n\r\n Utils.Write_Log ('Cat ' || i || ' : ' || g_cat_list(i).id || ' - ' || g_cat_list(i).min_items || ' - ' || g_cat_list(i).max_items || ' - ' || g_item_range_list(i).item_beg || ' - ' || g_item_range_list(i).item_end);\r\n\r\n END LOOP;\r\n\r\n g_sol_list.EXTEND (g_n_size);\r\n FOR i IN 1..g_n_size LOOP\r\n g_profit_hash (i) := i;\r\n END LOOP;\r\n g_nth_profit := g_profit_hash.FIRST;\r\n g_trial_sol.price := 0;\r\n g_trial_sol.profit := 0;\r\n\r\nEND Pop_Arrays;\r\n\r\nPROCEDURE Get_Best_Item_List (p_position PLS_INTEGER, p_item_index_beg PLS_INTEGER, p_item_index_end PLS_INTEGER, x_item_hash IN OUT NOCOPY int_hash_type) IS\r\n\r\nPROCEDURE Check_Item (p_item_index PLS_INTEGER) IS\r\n\r\n l_item_rec item_cat_rec_type := g_item_cat_list (p_item_index);\r\n l_item_list num_list_type;\r\n Item_Failed EXCEPTION;\r\n l_item_str VARCHAR2(200) := LPad (l_item_rec.id, (p_position)*3, '.') || '-' || l_item_rec.cat_id || '-' || l_item_rec.price || '-' || l_item_rec.profit;\r\n\r\n FUNCTION Price_LB (p_position PLS_INTEGER) RETURN PLS_INTEGER IS\r\n BEGIN\r\n\r\n RETURN g_min_price_togo (p_position);\r\n \r\n END Price_LB;\r\n\r\n FUNCTION Profit_UB (p_position PLS_INTEGER) RETURN PLS_INTEGER IS\r\n BEGIN\r\n\r\n RETURN g_max_profit_togo (p_position);\r\n\r\n END Profit_UB;\r\n\r\nBEGIN\r\n\r\n IF l_item_rec.price + g_trial_sol.price + Price_LB (p_position) > g_max_price THEN\r\n\r\n l_item_str := l_item_str || ' [price failed ' || (l_item_rec.price + g_trial_sol.price) || ']';\r\n IF (g_set_size - p_position) = 0 THEN\r\n Write_Log ('Solution fails with price of ' || (l_item_rec.price + g_trial_sol.price), 1);\r\n END IF;\r\n RAISE Item_Failed;\r\n END IF;\r\n\r\n IF l_item_rec.profit + g_trial_sol.profit + Profit_UB (p_position) <= g_nth_profit THEN\r\n l_item_str := l_item_str || ' [profit failed ' || (l_item_rec.profit + g_trial_sol.profit) || ', nth = ' || g_nth_profit || ']';\r\n IF (g_set_size - p_position) = 0 THEN\r\n Write_Log ('Solution fails with profit of ' || (l_item_rec.profit + g_trial_sol.profit), 1);\r\n g_n_sols := g_n_sols + 1;\r\n END IF;\r\n RAISE Item_Failed;\r\n END IF;\r\n\r\n x_item_hash (Dedup_Hash (p_card => g_keep_size, p_key => l_item_rec.profit + g_trial_sol.profit, p_hash => x_item_hash)) := p_item_index;\r\n\r\nEXCEPTION\r\n\r\n WHEN Item_Failed THEN\r\n Write_Log (l_item_str, 2);\r\n \r\nEND Check_Item;\r\n\r\nBEGIN\r\n\r\n FOR i IN p_item_index_beg..p_item_index_end LOOP\r\n\r\n Check_Item (i);\r\n\r\n END LOOP;\r\n\r\nEND Get_Best_Item_List;\r\n\r\nPROCEDURE Add_Solution IS\r\n l_nth_index PLS_INTEGER;\r\nBEGIN\r\n\r\n g_n_sols := g_n_sols + 1;\r\n l_nth_index := g_profit_hash (g_profit_hash.FIRST);\r\n Write_Log ('Solution replaces in position ' || l_nth_index || ' profit is ' || g_trial_sol.profit || ' price is ' || g_trial_sol.price, 1);\r\n\r\n g_profit_hash.DELETE (g_profit_hash.FIRST);\r\n g_profit_hash (Dedup_Hash (p_card => g_n_size, p_key => g_trial_sol.profit, p_hash => g_profit_hash)) := l_nth_index;\r\n\r\n g_sol_list (l_nth_index) := g_trial_sol;\r\n g_nth_profit := g_profit_hash.FIRST \/ g_n_size;\r\n\r\n IF Mod (g_n_sols, c_hash_renew_point) = 0 THEN -- Not sur eif this works, but is intended to clear memory overhang\r\n g_hash_buffer := g_profit_hash;\r\n g_profit_hash := g_hash_buffer;\r\n END IF;\r\n\r\nEND Add_Solution;\r\n\r\nPROCEDURE Add_Item_To_Trial (p_position PLS_INTEGER, p_item_index PLS_INTEGER) IS\r\n\r\n l_item_rec item_cat_rec_type := g_item_cat_list (p_item_index);\r\n\r\nBEGIN\r\n\r\n g_trial_sol.price := g_trial_sol.price + l_item_rec.price;\r\n g_trial_sol.profit := g_trial_sol.profit + l_item_rec.profit;\r\n\r\n IF g_trial_sol.item_list IS NULL THEN\r\n g_trial_sol.item_list := id_list_type (l_item_rec.id);\r\n ELSE\r\n g_trial_sol.item_list.EXTEND;\r\n g_trial_sol.item_list (p_position) := l_item_rec.id;\r\n END IF;\r\n\r\n IF p_position = g_set_size THEN\r\n\r\n Add_Solution;\r\n\r\n END IF;\r\n \r\nEND Add_Item_To_Trial;\r\n\r\nFUNCTION Try_Position (p_position PLS_INTEGER, p_n_curr_cat PLS_INTEGER, p_cat_index_beg PLS_INTEGER, p_item_index_beg PLS_INTEGER) RETURN BOOLEAN IS\r\n\r\n l_item_hash int_hash_type;\r\n l_item_index PLS_INTEGER;\r\n l_cat_index_beg PLS_INTEGER := p_cat_index_beg;\r\n l_item_index_beg PLS_INTEGER := p_item_index_beg;\r\n l_n_curr_cat PLS_INTEGER := p_n_curr_cat;\r\n l_profit PLS_INTEGER;\r\nBEGIN\r\n\r\n g_n_recursive_calls := g_n_recursive_calls + 1;\r\n IF g_n_recursive_calls > g_max_calls THEN\r\n Write_Log (LPad ('*', p_position, '*') || 'Truncating search after ' || g_max_calls || ' recursive calls***');\r\n RETURN TRUE;\r\n END IF;\r\n\r\n IF p_n_curr_cat = g_cat_list (p_cat_index_beg).max_items THEN\r\n-- \r\n-- passed in the cat we were on in last position\r\n-- check max not passed, if so go to next cat and reset item range\r\n--\r\n Write_Log ('Maxed Cat ' || p_cat_index_beg || ': ' || p_n_curr_cat || '-' || g_cat_list (p_cat_index_beg).max_items, 5);\r\n l_cat_index_beg := p_cat_index_beg + 1;\r\n IF l_cat_index_beg > g_n_cats THEN\r\n RETURN FALSE;\r\n END IF;\r\n l_item_index_beg := g_item_range_list (l_cat_index_beg).item_beg;\r\n l_n_curr_cat := 0;\r\n\r\n END IF;\r\n\r\n FOR j IN l_cat_index_beg..g_n_cats LOOP\r\n\r\n IF l_item_index_beg < g_item_range_list (j).item_beg THEN\r\n l_item_index_beg := g_item_range_list (j).item_beg;\r\n END IF;\r\n\r\n Write_Log ('Start Cat ' || j || ': ' || l_n_curr_cat || '-' || g_cat_list(j).min_items, 5);\r\n l_n_curr_cat := l_n_curr_cat + 1;\r\n l_item_hash.DELETE;\r\n Get_Best_Item_List (p_position => p_position, p_item_index_beg => l_item_index_beg, p_item_index_end => g_item_range_list(j).item_end, x_item_hash => l_item_hash);\r\n IF l_item_hash IS NOT NULL THEN\r\n\r\n l_profit := l_item_hash.LAST;\r\n FOR i IN 1..Least (g_keep_size, l_item_hash.COUNT) LOOP\r\n l_item_index := l_item_hash (l_profit);\r\n Write_Log (LPad (g_item_cat_list (l_item_index).id, (p_position)*3, '.') || '-' || g_item_cat_list (l_item_index).cat_id || '-' || g_item_cat_list (l_item_index).price || '-' || g_item_cat_list (l_item_index).profit, 1);\r\n Add_Item_To_Trial (p_position => p_position, p_item_index => l_item_index);\r\n IF p_position < g_set_size THEN\r\n\r\n IF Try_Position (p_position => p_position + 1, p_n_curr_cat => l_n_curr_cat, p_cat_index_beg => j, p_item_index_beg => l_item_index + 1) THEN RETURN TRUE; END IF;\r\n\r\n END IF;\r\n\r\n IF g_trial_sol.item_list IS NOT NULL AND g_trial_sol.item_list.COUNT = p_position THEN\r\n g_trial_sol.item_list.TRIM;\r\n g_trial_sol.price := g_trial_sol.price - g_item_cat_list (l_item_index).price;\r\n g_trial_sol.profit := g_trial_sol.profit - g_item_cat_list (l_item_index).profit;\r\n END IF;\r\n\r\n l_profit := l_item_hash.PRIOR (l_profit);\r\n\r\n END LOOP;\r\n\r\n ELSE\r\n Write_Log ('No items found');\r\n END IF;\r\n-- \r\n-- Don't look at any more cats if we are not past the minimum for the current one at this position\r\n--\r\n Write_Log ('Cat ' || j || ': ' || l_n_curr_cat || '-' || g_cat_list(j).min_items, 5);\r\n IF l_n_curr_cat <= g_cat_list(j).min_items THEN\r\n EXIT;\r\n END IF;\r\n\r\n l_n_curr_cat := 0;\r\n\r\n END LOOP;\r\n RETURN FALSE;\r\n\r\nEND Try_Position;\r\n\r\nFUNCTION Best_N_Sets ( p_keep_size PLS_INTEGER, \r\n p_max_calls PLS_INTEGER, \r\n p_n_size PLS_INTEGER, \r\n p_max_price PLS_INTEGER, \r\n p_cat_cur SYS_REFCURSOR, \r\n p_item_cur SYS_REFCURSOR) RETURN sol_detail_list_type PIPELINED IS\r\n\r\n l_sol_detail_rec sol_detail_rec_type;\r\n l_position PLS_INTEGER := 1;\r\nBEGIN\r\n\r\n g_keep_size := p_keep_size; g_max_calls := p_max_calls; g_n_size := p_n_size; g_max_price := p_max_price;\r\n\r\n Pop_Arrays (p_cat_cur, p_item_cur);\r\n\r\n IF Try_Position (p_position => 1, p_n_curr_cat => 0, p_cat_index_beg => 1, p_item_index_beg => 1) THEN NULL; END IF;\r\n\r\n FOR i IN 1..g_n_size LOOP\r\n\r\n l_sol_detail_rec.set_id := i;\r\n l_sol_detail_rec.sol_price := g_sol_list(i).price;\r\n l_sol_detail_rec.sol_profit := g_sol_list(i).profit;\r\n\r\n IF g_sol_list(i).item_list IS NOT NULL THEN\r\n\r\n FOR j IN 1..g_sol_list(i).item_list.COUNT LOOP\r\n\r\n l_sol_detail_rec.item_id := g_sol_list(i).item_list(j);\r\n PIPE ROW (l_sol_detail_rec);\r\n\r\n END LOOP;\r\n\r\n END IF;\r\n\r\n END LOOP;\r\n\r\n Write_Log (g_n_sols || ' solutions found in ' || g_n_recursive_calls || ' recursive calls');\r\n\r\n RETURN;\r\n\r\nEND Best_N_Sets;\r\n\r\nEND Item_Cats;\r\n\/\r\nSHO ERR\r\n<\/pre>\n<\/div>\nHow It Works<\/em><\/p>\nThe solution approach uses a modified depth-first recursion, following a similar idea to the SQL method, of adding items in strictly increasing order of category and profit ranking. Treatment of constraints uses similar ideas to the SQL solution.<\/p>\n
\n- The package is completely generic, with the items and categories being specified by means of input cursors<\/li>\n
- Depth-first is modified by a ranking of the next sets of feasible items, partitioned by category, in order to limit the number progressed<\/li>\n
- Hashes (associative arrays in Oracle) are used for ranking<\/li>\n
- A function, Dedup_Hash is used to allow for duplicate hash keys; it works by storing as key the actual key multiplied by the ranking set cardinality, then adding one iteratively until no duplication occurs<\/li>\n
- The recursion is truncated if the number of recursive calls exceeds an input limit<\/li>\n
- The input cursors are read into arrays and all subsequent processing is in memory; this is not a scalability problem because only the current best solutions are retained; also, I reset hashes after a given number of updates<\/li>\n<\/ul>\n
Results<\/strong><\/p>\nTest Problem 1: Brazilian League<\/em><\/p>\nThe pipelined function solved this in 5 seconds, while the SQL solution solved it in 21 seconds. The solutions were identical, as follows:<\/p>\n
\n
\r\nTOT_PROFIT TOT_PRICE RNK PO P_ID PLAYER_NAME CLUB_NAME PRICE AVG_POINTS\r\n---------- ---------- ---------- -- ---- ------------------------------ ------------------------------ ---------- ----------\r\n 10923 18176 1 CB 098 Dig\u00e3o Fluminense 931 927\r\n 099 Samir Flamengo 267 680\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 022 Wilson Vit\u00f3ria 1239 794\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 039 Elsinho Vasco 1468 850\r\n 19027 2 CB 098 Dig\u00e3o Fluminense 931 927\r\n 099 Samir Flamengo 267 680\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 021 F\u00e1bio Cruzeiro 2090 794\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 039 Elsinho Vasco 1468 850\r\n 10905 18795 3 CB 098 Dig\u00e3o Fluminense 931 927\r\n 099 Samir Flamengo 267 680\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 023 Vanderlei Coritiba 1858 776\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 039 Elsinho Vasco 1468 850\r\n 10833 18994 4 CB 098 Dig\u00e3o Fluminense 931 927\r\n 102 Bressan Gr\u00eamio 1085 590\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 022 Wilson Vit\u00f3ria 1239 794\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 039 Elsinho Vasco 1468 850\r\n 19845 5 CB 098 Dig\u00e3o Fluminense 931 927\r\n 102 Bressan Gr\u00eamio 1085 590\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 021 F\u00e1bio Cruzeiro 2090 794\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 039 Elsinho Vasco 1468 850\r\n 10831 19608 6 CB 098 Dig\u00e3o Fluminense 931 927\r\n 103 Manoel Atl\u00e9tico-PR 1699 588\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 022 Wilson Vit\u00f3ria 1239 794\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 039 Elsinho Vasco 1468 850\r\n 10825 18190 7 CB 098 Dig\u00e3o Fluminense 931 927\r\n 099 Samir Flamengo 267 680\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 022 Wilson Vit\u00f3ria 1239 794\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 040 Eg\u00eddio Cruzeiro 1482 752\r\n 19041 8 CB 098 Dig\u00e3o Fluminense 931 927\r\n 099 Samir Flamengo 267 680\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 021 F\u00e1bio Cruzeiro 2090 794\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 040 Eg\u00eddio Cruzeiro 1482 752\r\n 10821 19370 9 CB 098 Dig\u00e3o Fluminense 931 927\r\n 104 Cl\u00e9ber Ponte Preta 1461 578\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 022 Wilson Vit\u00f3ria 1239 794\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 039 Elsinho Vasco 1468 850\r\n 10815 19613 10 CB 098 Dig\u00e3o Fluminense 931 927\r\n 102 Bressan Gr\u00eamio 1085 590\r\n CO 078 Jaime De AlMFda Flamengo 1156 803\r\n FW 001 \u00c9derson Atl\u00e9tico-PR 1712 1012\r\n 002 Maxi Biancucchi Vit\u00f3ria 1962 1005\r\n 003 Rafael Sobis Fluminense 2303 955\r\n GK 023 Vanderlei Coritiba 1858 776\r\n MF 058 Fred Internacional 3028 892\r\n 059 Z\u00e9 Roberto Gr\u00eamio 2593 878\r\n 060 Otavinho Internacional 762 807\r\n WB 038 Ivan Portuguesa 755 1320\r\n 039 Elsinho Vasco 1468 850\r\n\r\n120 rows selected.\r\n<\/pre>\n<\/div>\nTest Problem 2: English Premier League<\/em><\/p>\nI used a maximum price of 900, and a keep parameter of 40, meaning retain the best 40 records by partition during recursion for the SQL and a value of 10 for the pipelined function. The keep parameter operates differently in the two cases so does not need to be the same value.<\/p>\n
The SQL solution took 98 seconds, while the pipelined function took 290 seconds. Both methods got the same best solution, but the tenth best was marginally better for the SQL, at 1965, compared with 1962 for pipelined function (which truncated after 100000 recursive calls).<\/p>\n
[For followers of Manchester United, and David Moyes, it may be of interest to note that all of the best solutions included both Leighton Baines and Patrice Evra, and the best also had Marouane Fellaini. Will these players be united also in the real world next season?]<\/p>\n
SQL Solution<\/em><\/p>\n\n
\r\nTOT_PROFIT TOT_PRICE RNK PO P_ID PLAYER_NAME CLUB_NAME PRICE AVG_POINTS\r\n---------- ---------- ---------- -- ---- ------------------------------ --------------- ---------- ----------\r\n 1973 898 1 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 268 Glen Johnson Liverpool 65 141\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n GK 549 Asmir Begovic Stoke City 56 154\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 265 Steven Gerrard Liverpool 92 187\r\n 641 Miguel Michu Swansea 79 169\r\n 177 Marouane Fellaini Everton 73 168\r\n 1971 899 2 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 268 Glen Johnson Liverpool 65 141\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n 047 Christian Benteke Aston Villa 74 166\r\n GK 549 Asmir Begovic Stoke City 56 154\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 265 Steven Gerrard Liverpool 92 187\r\n 641 Miguel Michu Swansea 79 169\r\n 1970 893 3 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 268 Glen Johnson Liverpool 65 141\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n 047 Christian Benteke Aston Villa 74 166\r\n GK 549 Asmir Begovic Stoke City 56 154\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 265 Steven Gerrard Liverpool 92 187\r\n 177 Marouane Fellaini Everton 73 168\r\n 1968 899 4 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 268 Glen Johnson Liverpool 65 141\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n 047 Christian Benteke Aston Villa 74 166\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 265 Steven Gerrard Liverpool 92 187\r\n 177 Marouane Fellaini Everton 73 168\r\n 428 Robert Snodgrass Norwich 62 152\r\n 5 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 569 Ryan Shawcross Stoke City 56 133\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n GK 549 Asmir Begovic Stoke City 56 154\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 149 Juan Mata Chelsea 102 190\r\n 641 Miguel Michu Swansea 79 169\r\n 177 Marouane Fellaini Everton 73 168\r\n 900 6 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 268 Glen Johnson Liverpool 65 141\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n 204 Dimitar Berbatov Fulham 71 161\r\n GK 549 Asmir Begovic Stoke City 56 154\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 149 Juan Mata Chelsea 102 190\r\n 177 Marouane Fellaini Everton 73 168\r\n 1966 896 7 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 268 Glen Johnson Liverpool 65 141\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n 204 Dimitar Berbatov Fulham 71 161\r\n GK 549 Asmir Begovic Stoke City 56 154\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 265 Steven Gerrard Liverpool 92 187\r\n 641 Miguel Michu Swansea 79 169\r\n 900 8 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 569 Ryan Shawcross Stoke City 56 133\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n 047 Christian Benteke Aston Villa 74 166\r\n GK 549 Asmir Begovic Stoke City 56 154\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 149 Juan Mata Chelsea 102 190\r\n 641 Miguel Michu Swansea 79 169\r\n 1965 890 9 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 268 Glen Johnson Liverpool 65 141\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n 204 Dimitar Berbatov Fulham 71 161\r\n GK 549 Asmir Begovic Stoke City 56 154\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 265 Steven Gerrard Liverpool 92 187\r\n 177 Marouane Fellaini Everton 73 168\r\n 894 10 DF 165 Leighton Baines Everton 78 173\r\n 332 Patrice Evra Man Utd 73 152\r\n 569 Ryan Shawcross Stoke City 56 133\r\n FW 286 Luis Suarez Liverpool 105 213\r\n 533 Rickie Lambert Southampton 69 178\r\n 047 Christian Benteke Aston Villa 74 166\r\n GK 549 Asmir Begovic Stoke City 56 154\r\n MF 661 Gareth Bale Tottenham 111 240\r\n 030 Santi Santi Cazorla Arsenal 97 198\r\n 149 Juan Mata Chelsea 102 190\r\n 177 Marouane Fellaini Everton 73 168\r\n\r\n110 rows selected.\r\n\r\nElapsed: 00:01:38.26\r\n<\/pre>\n<\/div>\nPipelined Function Solution<\/em><\/p>\n\n
\r\nSOL_PROFIT SOL_PRICE RNK PO ITEM_ID CLUB_NAME PLAYER_NAME PRICE AVG_POINTS\r\n---------- ---------- ---------- -- ---------- --------------- -------------------- ---------- ----------\r\n 1973 898 1 DF 165 Everton Leighton Baines 78 173\r\n 268 Liverpool Glen Johnson 65 141\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 286 Liverpool Luis Suarez 105 213\r\n 533 Southampton Rickie Lambert 69 178\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 177 Everton Marouane Fellaini 73 168\r\n 265 Liverpool Steven Gerrard 92 187\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 641 Swansea Miguel Michu 79 169\r\n 661 Tottenham Gareth Bale 111 240\r\n 1971 899 2 DF 165 Everton Leighton Baines 78 173\r\n 268 Liverpool Glen Johnson 65 141\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 286 Liverpool Luis Suarez 105 213\r\n 47 Aston Villa Christian Benteke 74 166\r\n 533 Southampton Rickie Lambert 69 178\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 265 Liverpool Steven Gerrard 92 187\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 641 Swansea Miguel Michu 79 169\r\n 661 Tottenham Gareth Bale 111 240\r\n 1970 893 3 DF 165 Everton Leighton Baines 78 173\r\n 268 Liverpool Glen Johnson 65 141\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 286 Liverpool Luis Suarez 105 213\r\n 47 Aston Villa Christian Benteke 74 166\r\n 533 Southampton Rickie Lambert 69 178\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 177 Everton Marouane Fellaini 73 168\r\n 265 Liverpool Steven Gerrard 92 187\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 661 Tottenham Gareth Bale 111 240\r\n 1968 900 4 DF 165 Everton Leighton Baines 78 173\r\n 268 Liverpool Glen Johnson 65 141\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 204 Fulham Dimitar Berbatov 71 161\r\n 286 Liverpool Luis Suarez 105 213\r\n 533 Southampton Rickie Lambert 69 178\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 149 Chelsea Juan Mata 102 190\r\n 177 Everton Marouane Fellaini 73 168\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 661 Tottenham Gareth Bale 111 240\r\n 1966 896 5 DF 165 Everton Leighton Baines 78 173\r\n 268 Liverpool Glen Johnson 65 141\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 204 Fulham Dimitar Berbatov 71 161\r\n 286 Liverpool Luis Suarez 105 213\r\n 533 Southampton Rickie Lambert 69 178\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 265 Liverpool Steven Gerrard 92 187\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 641 Swansea Miguel Michu 79 169\r\n 661 Tottenham Gareth Bale 111 240\r\n 1965 890 6 DF 165 Everton Leighton Baines 78 173\r\n 268 Liverpool Glen Johnson 65 141\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 204 Fulham Dimitar Berbatov 71 161\r\n 286 Liverpool Luis Suarez 105 213\r\n 533 Southampton Rickie Lambert 69 178\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 177 Everton Marouane Fellaini 73 168\r\n 265 Liverpool Steven Gerrard 92 187\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 661 Tottenham Gareth Bale 111 240\r\n 897 7 DF 165 Everton Leighton Baines 78 173\r\n 248 Liverpool Daniel Agger 64 133\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 286 Liverpool Luis Suarez 105 213\r\n 533 Southampton Rickie Lambert 69 178\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 177 Everton Marouane Fellaini 73 168\r\n 265 Liverpool Steven Gerrard 92 187\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 641 Swansea Miguel Michu 79 169\r\n 661 Tottenham Gareth Bale 111 240\r\n 1964 895 8 DF 165 Everton Leighton Baines 78 173\r\n 268 Liverpool Glen Johnson 65 141\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 286 Liverpool Luis Suarez 105 213\r\n 533 Southampton Rickie Lambert 69 178\r\n 720 West Brom Romelu Lukaku 66 157\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 149 Chelsea Juan Mata 102 190\r\n 177 Everton Marouane Fellaini 73 168\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 661 Tottenham Gareth Bale 111 240\r\n 1963 898 9 DF 165 Everton Leighton Baines 78 173\r\n 248 Liverpool Daniel Agger 64 133\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 286 Liverpool Luis Suarez 105 213\r\n 47 Aston Villa Christian Benteke 74 166\r\n 533 Southampton Rickie Lambert 69 178\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 265 Liverpool Steven Gerrard 92 187\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 641 Swansea Miguel Michu 79 169\r\n 661 Tottenham Gareth Bale 111 240\r\n 1962 891 10 DF 165 Everton Leighton Baines 78 173\r\n 268 Liverpool Glen Johnson 65 141\r\n 332 Man Utd Patrice Evra 73 152\r\n FW 286 Liverpool Luis Suarez 105 213\r\n 533 Southampton Rickie Lambert 69 178\r\n 720 West Brom Romelu Lukaku 66 157\r\n GK 549 Stoke City Asmir Begovic 56 154\r\n MF 265 Liverpool Steven Gerrard 92 187\r\n 30 Arsenal Santi Santi Cazorla 97 198\r\n 641 Swansea Miguel Michu 79 169\r\n 661 Tottenham Gareth Bale 111 240\r\n\r\n110 rows selected.\r\n\r\nElapsed: 00:04:49.92\r\n<\/pre>\n<\/div>\nConclusions<\/strong><\/p>\nMy idea for using recursive subquery factoring to solve combinatorial optimisation problems, such as knapsack problems, described in other articles on my blog, was previously only practical for small problems. The extensions described here render it a practical proposition even for larger problems. It is also relatively simple compared with procedural approaches.<\/p>\n
<\/p>\n