28 November 2024 12:39:58 PM knapsack_brute_test(): C version Test knapsack_brute() subset_next_test(): Test subset_next() Generate in order subsets of size 5 0: 0 0 0 0 0 1: 0 0 0 0 1 2: 0 0 0 1 0 3: 0 0 0 1 1 4: 0 0 1 0 0 5: 0 0 1 0 1 6: 0 0 1 1 0 7: 0 0 1 1 1 8: 0 1 0 0 0 9: 0 1 0 0 1 10: 0 1 0 1 0 11: 0 1 0 1 1 12: 0 1 1 0 0 13: 0 1 1 0 1 14: 0 1 1 1 0 15: 0 1 1 1 1 16: 1 0 0 0 0 17: 1 0 0 0 1 18: 1 0 0 1 0 19: 1 0 0 1 1 20: 1 0 1 0 0 21: 1 0 1 0 1 22: 1 0 1 1 0 23: 1 0 1 1 1 24: 1 1 0 0 0 25: 1 1 0 0 1 26: 1 1 0 1 0 27: 1 1 0 1 1 28: 1 1 1 0 0 29: 1 1 1 0 1 30: 1 1 1 1 0 31: 1 1 1 1 1 knapsack_brute_test01(): knapsack_brute() uses a brute force approach. Maximize profit without exceeding weight limit. Problem 1 Number of items is 5 Knapsack weight limit is 26 Item 0/1 Value Weight Density 0 0 24 12 2 1 1 13 7 1.85714 2 1 23 11 2.09091 3 1 15 8 1.875 4 0 16 9 1.77778 Taken 3 51 26 1.96154 Problem 2 Number of items is 6 Knapsack weight limit is 190 Item 0/1 Value Weight Density 0 1 50 56 0.892857 1 1 50 59 0.847458 2 0 64 80 0.8 3 0 46 64 0.71875 4 1 50 75 0.666667 5 0 5 17 0.294118 Taken 3 150 190 0.789474 Problem 3 Number of items is 6 Knapsack weight limit is 20 Item 0/1 Value Weight Density 0 1 175 10 17.5 1 1 90 9 10 2 0 20 4 5 3 0 50 2 25 4 1 10 1 10 5 0 200 20 10 Taken 3 275 20 13.75 Problem 4 Number of items is 7 Knapsack weight limit is 50 Item 0/1 Value Weight Density 0 1 70 31 2.25806 1 0 20 10 2 2 0 39 20 1.95 3 1 37 19 1.94737 4 0 7 4 1.75 5 0 5 3 1.66667 6 0 10 6 1.66667 Taken 2 107 50 2.14 Problem 5 Number of items is 7 Knapsack weight limit is 170 Item 0/1 Value Weight Density 0 0 442 41 10.7805 1 1 525 50 10.5 2 0 511 49 10.4286 3 1 593 59 10.0508 4 0 546 55 9.92727 5 0 564 57 9.89474 6 1 617 60 10.2833 Taken 3 1735 169 10.2663 Problem 6 Number of items is 8 Knapsack weight limit is 104 Item 0/1 Value Weight Density 0 1 350 25 14 1 0 400 35 11.4286 2 1 450 45 10 3 1 20 5 4 4 1 70 25 2.8 5 0 8 3 2.66667 6 1 5 2 2.5 7 1 5 2 2.5 Taken 6 900 104 8.65385 Problem 7 Number of items is 10 Knapsack weight limit is 67 Item 0/1 Value Weight Density 0 1 505 23 21.9565 1 0 352 26 13.5385 2 0 458 20 22.9 3 1 220 18 12.2222 4 0 354 32 11.0625 5 0 414 27 15.3333 6 0 498 29 17.1724 7 1 545 26 20.9615 8 0 473 30 15.7667 9 0 543 27 20.1111 Taken 3 1270 67 18.9552 Problem 8 Number of items is 10 Knapsack weight limit is 165 Item 0/1 Value Weight Density 0 1 92 23 4 1 1 57 31 1.83871 2 1 49 29 1.68966 3 1 68 44 1.54545 4 0 60 53 1.13208 5 1 43 38 1.13158 6 0 67 63 1.06349 7 0 84 85 0.988235 8 0 87 89 0.977528 9 0 72 82 0.878049 Taken 5 309 165 1.87273 Problem 9 Number of items is 15 Knapsack weight limit is 750 Item 0/1 Value Weight Density 0 1 135 70 1.92857 1 0 139 73 1.90411 2 1 149 77 1.93506 3 0 150 80 1.875 4 1 156 82 1.90244 5 0 163 87 1.87356 6 1 173 90 1.92222 7 1 184 94 1.95745 8 1 192 98 1.95918 9 0 201 106 1.89623 10 0 210 110 1.90909 11 0 214 113 1.89381 12 0 221 115 1.92174 13 1 229 118 1.94068 14 1 240 120 2 Taken 8 1458 749 1.9466 Problem 10 Number of items is 24 Knapsack weight limit is 6404180 Item 0/1 Value Weight Density 0 1 825594 382745 2.15703 1 1 1677009 799601 2.09731 2 0 1676628 909247 1.84397 3 1 1523970 729069 2.0903 4 1 943972 467902 2.01746 5 1 97426 44328 2.19784 6 0 69666 34610 2.01289 7 0 1296457 698150 1.85699 8 0 1679693 823460 2.0398 9 1 1902996 903959 2.10518 10 1 1844992 853665 2.16126 11 0 1049289 551830 1.90147 12 1 1252836 610856 2.05095 13 0 1319836 670702 1.96784 14 0 953277 488960 1.9496 15 1 2067538 951111 2.17381 16 0 675367 323046 2.09062 17 0 853655 446298 1.91275 18 0 1826027 931161 1.96102 19 0 65731 31385 2.09434 20 0 901489 496951 1.81404 21 1 577243 264724 2.18055 22 1 466257 224916 2.07303 23 1 369261 169684 2.17617 Taken 12 13549094 6402560 2.1162 knapsack_brute_test(): Normal end of execution. 28 November 2024 12:40:01 PM