124 Knapsack Backtracking
Back to General discussions forum
Hi,
my program gets a WRONG with the message
"Total weight of chosen items is 1532 which is greater than allowed 1508"
but the results of the program are
totalv 3761 (total velue) totalw 1508 (total weight) result 3761 (maximum value)
which seem to be correct.
Any hint would be greatly appreciated!
Thank you
I see your solution in your failed attempts list. Can you post what input set gave you the results you posted?
Now I get
Item # 0 was used more than once!
for the following solution (line breaks added for post)
0 1 3 4 5 6 8 9 11 12 13 18 21 22 23 26 27 28 29 30 31 32 34 35 36 37 39 40 42 43 44 45 46 48 49 51 52 53 54 55 56 57 58 61 62 64 66 67 73 74 75 76 77 79 81 82 85 86 87 89 90 91 93 94 96 97 102 103 105 106 107 108 109 111 114 115 116 117 118 122 124 126 127 128 130 133
Total weight: 1544, total value 3590
Input data: 134 1544 11 29 14 36 9 10 22 43 25 67 20 41 12 33 28 28 19 46 21 52 25 38 12 33 14 27 23 58 27 35 26 31 29 41 27 34 12 25 21 25 14 19 21 49 6 13 22 50 11 17 14 15 19 45 28 81 8 18 23 69 24 50 7 17 24 71 26 28 18 35 8 23 22 57 19 47 13 19 14 31 18 45 21 25 16 33 6 13 8 20 19 54 12 28 21 22 21 41 7 9 29 43 6 13 5 12 13 22 27 65 29 53 16 34 18 51 7 15 17 26 13 13 9 20 23 61 21 35 12 30 18 26 30 65 26 78 11 14 14 17 27 43 18 29 27 30 10 30 21 50 11 33 23 43 20 36 11 16 24 50 30 46 24 71 27 59 29 34 24 39 10 22 21 52 29 57 25 32 17 32 26 63 15 31 8 8 29 51 11 27 28 41 30 71 10 27 12 16 28 29 17 21 21 25 27 57 20 46 23 24 6 12 24 47 6 17 17 51 11 28 22 30 30 70 27 37 17 22 13 23 9 24 18 47 28 49 14 28 5 5 18 21 19 29 19 42 9 10 20 37 26 40 20 52 29 57 30 55 21 34 26 68 8 14 20 22 23 67
OK, got it!
There was an extra space at the end of the solution.
Thanks for trying to help.
I get the following:
Item # 0 was used more than once! as error message.
My answer was: 0 1 2 4 5 6 7 8 9 11 12 13 15 16 17 18 19 21 24 25 26 27 30 32 34 35 36 37 39 40 42 43 45 46 47 48 49 50 51 53 54 55 57 59 61 63 64 66 67 68 69 70 71 73 74 75 76 77 78 79 83 85 86 89 91 92 93 95 97 98 99 100 101 102 103 105 106 110 114 115 119 121 125 128 129 131
Input Data was: 133 1403 19 30 5 13 29 59 27 35 15 30 23 54 17 42 14 35 20 33 25 49 7 11 15 39 12 21 5 10 27 40 10 29 14 38 19 57 30 82 18 51 21 23 5 14 12 12 26 39 7 17 27 62 27 48 28 70 8 11 16 16 10 18 18 23 9 17 18 20 20 51 24 42 22 57 24 70 14 18 30 49 14 41 30 41 24 57 20 58 15 19 11 31 28 57 12 27 6 14 22 39 15 33 11 26 29 29 14 30 18 40 21 50 11 11 5 14 16 20 15 40 6 9 24 45 16 18 19 31 15 32 26 36 7 17 8 16 13 28 15 32 7 15 12 33 11 12 7 20 21 42 17 34 23 50 20 57 11 33 8 18 8 8 24 35 30 30 14 30 13 20 7 16 13 22 6 6 19 21 28 46 23 27 7 14 9 17 16 46 5 7 28 60 11 16 11 26 7 13 12 24 14 31 24 60 21 45 11 28 22 25 29 84 15 24 16 21 14 14 13 21 9 27 29 46 15 16 23 24 26 48 18 38 9 12 24 25 7 11 22 54 14 19 10 28 6 8 5 6 12 16 29 72 13 19 8 12 17 27 10 20 22 23 10 19 24 35
The sum of weights from my answer is 1403. (Which is equal to max weight) The sum of values is 3166. The language I am using is Julia v1.8.4
Hi Friend! Judging by similar complaint above this may happen due to spare spaces. Not sure if it was your case but I slightly edited task checker to be more tolerant. Please retry.
Interestingly, the solution I get for this instance seems not to use item #0 and produces an overall value of 3,166 (but of course other soltuions can exist that use #0).
Heh. Comparably interesting is that solution in Julia seemingly doesn't include real solution, relying instead on library method :)
(checker however should work for any suitable solution as far as I remember)