Last active
May 8, 2020 09:22
-
-
Save TheRayTracer/4375786 to your computer and use it in GitHub Desktop.
An example implementation to solve the knapsack problem. This includes a 2D and 1D array solution.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| #include <fstream> | |
| #include <vector> | |
| #include <cassert> | |
| namespace std { } | |
| using namespace std; | |
| struct item | |
| { | |
| size_t value; | |
| size_t weight; | |
| }; | |
| istream& operator>>(istream& is, item& i) | |
| { | |
| return is >> i.value >> i.weight; | |
| } | |
| size_t knapsack_2d(vector<item>& store, const size_t capacity) | |
| { | |
| const size_t n = store.size() + 1; | |
| const size_t W = capacity + 1; | |
| vector<vector<size_t> > T; | |
| T.resize(n); | |
| for (size_t i = 0; i < n; T[i].resize(W), ++i); /* This is our 2D managed array.*/ | |
| for (size_t i = 0; i < W; T[0][i] = 0, ++i); | |
| for (size_t i = 0; i < store.size(); ++i) | |
| { | |
| for (size_t j = 0; j < W; ++j) | |
| { | |
| if (j >= store[i].weight) | |
| { | |
| T[i + 1][j] = max(T[i][j], T[i][j - store[i].weight] + store[i].value); | |
| } | |
| else | |
| { | |
| T[i + 1][j] = T[i][j]; | |
| } | |
| } | |
| } | |
| size_t value = T[store.size()][capacity]; | |
| return value; | |
| } | |
| size_t knapsack_1d(vector<item>& store, const size_t capacity) | |
| { | |
| const size_t W = capacity + 1; | |
| vector<size_t> T; | |
| T.resize(W); | |
| for (size_t i = 0; i < W; T[i] = 0, ++i); | |
| for (size_t i = 0; i < store.size(); ++i) | |
| { | |
| int __w64 t = capacity - store[i].weight; | |
| if (t >= 0) | |
| { | |
| for (int __w64 j = t; j >= 0; --j) | |
| { | |
| T[j + store[i].weight] = max(T[j + store[i].weight], T[j] + store[i].value); | |
| } | |
| } | |
| } | |
| return T[capacity]; | |
| } | |
| int main(int argc, char* argv[]) | |
| { | |
| vector<item> store; | |
| size_t capacity = 0, count = 0; | |
| if (argc > 1) | |
| { | |
| ifstream ifs; | |
| ifs.open(argv[1]); | |
| ifs >> capacity >> count; | |
| item i = {0}; | |
| while (ifs >> i) | |
| { | |
| store.push_back(i); | |
| } | |
| ifs.close(); | |
| } | |
| cout << "Input size: " << store.size() << endl; | |
| assert(store.size() == count); | |
| size_t value = knapsack_1d(store, capacity); | |
| cout << "Optimal Value: " << value << endl; | |
| assert(value == 2595819); | |
| cin.get(); | |
| return 0; | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 2000000 500 | |
| 16808 241486 | |
| 50074 834558 | |
| 8931 738037 | |
| 27545 212860 | |
| 77924 494349 | |
| 64441 815107 | |
| 84493 723724 | |
| 7988 421316 | |
| 82328 652893 | |
| 78841 402599 | |
| 44304 631607 | |
| 17710 318556 | |
| 29561 608119 | |
| 93100 429390 | |
| 51817 431959 | |
| 99098 365899 | |
| 13513 90282 | |
| 23811 467558 | |
| 80980 743542 | |
| 36580 896948 | |
| 11968 883369 | |
| 1394 604449 | |
| 25486 562244 | |
| 25229 333236 | |
| 40195 157443 | |
| 35002 696933 | |
| 16709 539123 | |
| 15669 202584 | |
| 88125 759690 | |
| 9531 69730 | |
| 27723 110467 | |
| 28550 651058 | |
| 97802 231944 | |
| 40978 186803 | |
| 8229 572887 | |
| 60299 797491 | |
| 28636 692529 | |
| 23866 503157 | |
| 39064 243688 | |
| 39426 182032 | |
| 24116 262772 | |
| 75630 246257 | |
| 46518 605917 | |
| 30106 685556 | |
| 19452 522241 | |
| 82189 419114 | |
| 99506 622799 | |
| 6753 512332 | |
| 36717 489578 | |
| 54439 869423 | |
| 51502 771067 | |
| 83872 884103 | |
| 11138 450309 | |
| 53178 444804 | |
| 22295 405168 | |
| 21610 527012 | |
| 59746 255432 | |
| 53636 702071 | |
| 98143 264607 | |
| 27969 227173 | |
| 261 471962 | |
| 41595 807033 | |
| 16396 471595 | |
| 19114 520773 | |
| 71007 21653 | |
| 97943 882635 | |
| 42083 801161 | |
| 30768 806299 | |
| 85696 402599 | |
| 73672 858413 | |
| 48591 122945 | |
| 14739 256166 | |
| 31617 350118 | |
| 55641 783545 | |
| 37336 518571 | |
| 97973 17616 | |
| 49096 640048 | |
| 83455 74134 | |
| 12290 610321 | |
| 48906 141662 | |
| 36124 589402 | |
| 45814 638947 | |
| 35239 751616 | |
| 96221 533618 | |
| 12367 850339 | |
| 25227 670142 | |
| 41364 699869 | |
| 7845 269378 | |
| 36551 198914 | |
| 8624 98356 | |
| 97386 122211 | |
| 95273 646654 | |
| 99248 231210 | |
| 13497 806666 | |
| 40624 153773 | |
| 28145 427188 | |
| 35736 90282 | |
| 61626 23855 | |
| 46043 585365 | |
| 54680 654728 | |
| 75245 593439 | |
| 78819 117073 | |
| 87693 903554 | |
| 12992 357458 | |
| 22670 469393 | |
| 89554 642617 | |
| 75826 568850 | |
| 29663 532884 | |
| 33809 531783 | |
| 22762 171022 | |
| 37336 833090 | |
| 77996 467191 | |
| 62768 784279 | |
| 29875 716017 | |
| 40557 519305 | |
| 68873 549766 | |
| 20095 435262 | |
| 13756 171022 | |
| 51408 709411 | |
| 30194 111935 | |
| 15681 116706 | |
| 16856 669408 | |
| 70964 512332 | |
| 86677 892544 | |
| 63250 836026 | |
| 77845 418747 | |
| 60809 531049 | |
| 28652 532884 | |
| 45204 478201 | |
| 96532 514167 | |
| 95420 866487 | |
| 42010 780976 | |
| 87930 258368 | |
| 44055 202217 | |
| 76738 877864 | |
| 47318 901352 | |
| 4201 634910 | |
| 21565 69730 | |
| 6649 16515 | |
| 25551 203685 | |
| 41977 835292 | |
| 38555 736202 | |
| 2505 215429 | |
| 34749 905022 | |
| 59379 171389 | |
| 78210 744276 | |
| 78554 485174 | |
| 50448 394158 | |
| 80774 697300 | |
| 64306 324061 | |
| 70054 724825 | |
| 84631 377643 | |
| 5401 191941 | |
| 95371 695098 | |
| 83017 107164 | |
| 8156 807033 | |
| 15558 218365 | |
| 53179 670142 | |
| 87358 219466 | |
| 27879 757121 | |
| 74820 194143 | |
| 83134 660600 | |
| 23721 531783 | |
| 6634 32663 | |
| 76032 528480 | |
| 60590 884470 | |
| 98878 569584 | |
| 79359 553436 | |
| 77255 80373 | |
| 14916 269378 | |
| 45481 776205 | |
| 69956 608853 | |
| 37108 143497 | |
| 40001 213961 | |
| 45036 344613 | |
| 61114 472696 | |
| 29594 539123 | |
| 98355 675647 | |
| 25358 809235 | |
| 13730 649223 | |
| 76564 218365 | |
| 60918 373606 | |
| 19420 63491 | |
| 47748 105696 | |
| 55396 600045 | |
| 4474 913096 | |
| 11749 417279 | |
| 5659 576190 | |
| 45407 777306 | |
| 39825 916399 | |
| 974 70097 | |
| 46898 715650 | |
| 3951 50646 | |
| 88481 562978 | |
| 13901 764828 | |
| 62534 772535 | |
| 17004 569217 | |
| 20951 344246 | |
| 58781 576557 | |
| 41833 484073 | |
| 33550 262405 | |
| 6250 548665 | |
| 66311 846302 | |
| 984 237082 | |
| 92041 86245 | |
| 73651 451043 | |
| 53230 873827 | |
| 17747 340209 | |
| 87231 470861 | |
| 70777 354889 | |
| 68245 560409 | |
| 47697 456181 | |
| 29065 364064 | |
| 56599 853642 | |
| 69941 86245 | |
| 89552 891443 | |
| 27206 238183 | |
| 80419 708677 | |
| 59650 713448 | |
| 83321 593439 | |
| 22013 800794 | |
| 54789 811070 | |
| 24009 64592 | |
| 65325 643718 | |
| 51258 547197 | |
| 35691 770333 | |
| 62411 360027 | |
| 90554 384983 | |
| 90961 242220 | |
| 51404 456181 | |
| 7308 263873 | |
| 44911 44774 | |
| 92800 210658 | |
| 20172 702438 | |
| 34415 522608 | |
| 16642 883002 | |
| 55349 229375 | |
| 14316 229375 | |
| 81446 587567 | |
| 72221 702071 | |
| 9240 681152 | |
| 41306 439666 | |
| 82254 569217 | |
| 15167 44040 | |
| 59305 492514 | |
| 45899 274516 | |
| 1721 647388 | |
| 51581 173591 | |
| 49353 713448 | |
| 78699 803363 | |
| 60812 626469 | |
| 56892 885204 | |
| 31729 70097 | |
| 51662 300940 | |
| 3121 193409 | |
| 17159 448107 | |
| 69628 266075 | |
| 53712 737303 | |
| 29595 767030 | |
| 1728 778774 | |
| 98796 623166 | |
| 37443 173958 | |
| 85007 28993 | |
| 66925 438198 | |
| 27098 28993 | |
| 67104 736202 | |
| 80109 49178 | |
| 2282 51013 | |
| 43711 456548 | |
| 1906 245890 | |
| 67782 447740 | |
| 70792 346815 | |
| 97866 424252 | |
| 29537 643351 | |
| 57126 605917 | |
| 80168 124413 | |
| 477 792353 | |
| 21577 216530 | |
| 77468 571419 | |
| 27385 373973 | |
| 25211 910160 | |
| 28212 37434 | |
| 19519 788316 | |
| 21935 671977 | |
| 80768 843366 | |
| 49819 30461 | |
| 11826 765562 | |
| 58029 693263 | |
| 78035 197813 | |
| 51241 914564 | |
| 86541 80006 | |
| 90936 640415 | |
| 48049 103127 | |
| 87012 148268 | |
| 53065 755286 | |
| 17238 601146 | |
| 70246 643351 | |
| 70416 446272 | |
| 24711 83676 | |
| 63038 601146 | |
| 68448 270846 | |
| 41694 471962 | |
| 67130 793454 | |
| 33980 25323 | |
| 95526 631974 | |
| 74959 279287 | |
| 11801 837127 | |
| 87671 310482 | |
| 80847 29727 | |
| 9544 481504 | |
| 85937 343145 | |
| 97720 712347 | |
| 91248 681519 | |
| 28360 177628 | |
| 45036 308647 | |
| 83913 383148 | |
| 45990 226072 | |
| 63735 870891 | |
| 520 608486 | |
| 67046 170288 | |
| 26662 853642 | |
| 82820 815474 | |
| 22904 485174 | |
| 36799 171022 | |
| 14005 75969 | |
| 680 373239 | |
| 7392 11377 | |
| 64925 211025 | |
| 57122 750148 | |
| 77107 175426 | |
| 51704 577658 | |
| 71033 300206 | |
| 61655 729596 | |
| 42218 330300 | |
| 57290 271580 | |
| 84748 344246 | |
| 89880 890342 | |
| 1517 266809 | |
| 82763 677482 | |
| 49040 687391 | |
| 5904 592338 | |
| 10762 475632 | |
| 61467 211025 | |
| 44558 659866 | |
| 26956 747579 | |
| 21495 751983 | |
| 92222 148635 | |
| 2294 546096 | |
| 42233 803730 | |
| 34792 782811 | |
| 49153 468292 | |
| 73571 862083 | |
| 27440 422784 | |
| 35800 547931 | |
| 91836 119642 | |
| 46044 903187 | |
| 74087 11744 | |
| 39151 263873 | |
| 18624 324428 | |
| 9606 760057 | |
| 37312 718953 | |
| 77993 321125 | |
| 38700 550133 | |
| 80640 181665 | |
| 25837 614358 | |
| 82858 9542 | |
| 83329 456548 | |
| 74411 253964 | |
| 85177 320391 | |
| 72092 745377 | |
| 84712 129551 | |
| 91027 364798 | |
| 10791 740973 | |
| 59365 256900 | |
| 24885 536554 | |
| 41442 323694 | |
| 16180 252863 | |
| 94538 438198 | |
| 87562 642250 | |
| 74166 892911 | |
| 57733 838228 | |
| 47855 547197 | |
| 9848 299105 | |
| 40463 519672 | |
| 43820 80006 | |
| 13378 225338 | |
| 43837 82942 | |
| 32300 419114 | |
| 34760 867588 | |
| 74391 500955 | |
| 30049 203685 | |
| 59045 26424 | |
| 40151 554904 | |
| 41296 197079 | |
| 95732 58720 | |
| 28246 573254 | |
| 46058 332135 | |
| 93929 177995 | |
| 62174 629038 | |
| 9670 147534 | |
| 4504 873827 | |
| 18676 450676 | |
| 24301 914197 | |
| 40263 659132 | |
| 68264 545729 | |
| 24890 524443 | |
| 76736 863551 | |
| 31365 262772 | |
| 50964 410306 | |
| 85653 263506 | |
| 57317 293233 | |
| 61421 58353 | |
| 7451 223136 | |
| 78742 240385 | |
| 99197 178729 | |
| 2502 619863 | |
| 93129 860248 | |
| 77449 41104 | |
| 17254 534352 | |
| 69330 184601 | |
| 33720 367367 | |
| 38821 862817 | |
| 81080 44407 | |
| 94411 366266 | |
| 66114 185702 | |
| 98139 389020 | |
| 46045 216163 | |
| 98394 321859 | |
| 981 538022 | |
| 45597 208089 | |
| 67371 397461 | |
| 6544 836393 | |
| 62853 536921 | |
| 76825 856211 | |
| 82381 835292 | |
| 71858 673445 | |
| 59499 253597 | |
| 52846 637479 | |
| 68510 375808 | |
| 96850 896214 | |
| 19291 907591 | |
| 85744 97989 | |
| 36386 749047 | |
| 86276 493248 | |
| 11152 843733 | |
| 75252 74134 | |
| 32784 804831 | |
| 66438 447740 | |
| 7699 873827 | |
| 83138 347549 | |
| 45879 875295 | |
| 70343 314519 | |
| 45961 662802 | |
| 35141 228641 | |
| 43567 609220 | |
| 563 114504 | |
| 41970 721889 | |
| 12624 847770 | |
| 17314 450309 | |
| 27011 782811 | |
| 76979 415811 | |
| 7395 42939 | |
| 87657 633075 | |
| 61787 423518 | |
| 54545 680051 | |
| 8777 22754 | |
| 74253 642984 | |
| 75515 14680 | |
| 95020 29360 | |
| 66672 310482 | |
| 56664 101292 | |
| 84025 546463 | |
| 16855 720788 | |
| 14982 751249 | |
| 86289 257267 | |
| 8360 856578 | |
| 55380 560776 | |
| 19462 674913 | |
| 8354 849238 | |
| 85789 906857 | |
| 69881 895847 | |
| 38284 303142 | |
| 237 855110 | |
| 98568 353054 | |
| 47940 451410 | |
| 69652 48811 | |
| 9267 640415 | |
| 111 11010 | |
| 86328 820245 | |
| 25582 745377 | |
| 7937 250661 | |
| 45436 715283 | |
| 66973 184234 | |
| 19799 778040 | |
| 74588 571786 | |
| 69090 86245 | |
| 29091 784646 | |
| 66613 883369 | |
| 72113 21653 | |
| 51952 540591 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment