beaunus/stanford-algs

Some test-cases have wrong results

Closed this issue · 4 comments

dgrcode commented

I think the discrepancy is caused by the remainin capacity for loop not reaching the full capacity of the knapsack. It seems like the loop goes as far as capacity - 1. Therefore the results are wrong if the solution for capacity C and C-1 are different, and are correct if both problems have the same solutions.

I'll post here some test-cases that I've tried, with the solution that I've found.

  • knapsack-example-w-10-n-10-solution-12.txt
    My solution: 14 (different)
    Items in the sack (starting at item 1): [1, 2, 4, 5, 7, 10]
    Total weight in the sack: 10
    Total value in the sack: 14

  • knapsack-example-w-10-n-10-solution-16.txt
    My solution: 18 (different)
    Items in the sack (starting at item 1): [3, 4, 5, 6, 7, 10]
    Total value in the sack: 18
    Total weight in the sack: 10

  • knapsack-example-w-100-n-10-solution-171.txt
    My solution: 171 (same)
    Items in the sack (starting at item 1): [3, 4, 6, 8, 10]
    Total value in the sack: 171
    Total weight in the sack: 122

  • knapsack-example-w-100-n-10-solution-187.txt
    My solution: 187 (same)
    Items in the sack (starting at item 1): [1, 3, 4, 6, 9]
    Total value in the sack: 187
    Total weight in the sack: 96

beaunus commented

Thank you very much for helping me with this.

Perhaps your idea about C-1 was correct, but I suspect that it was something different.

I think that the issue was that the weights were not strictly positive. I have adjusted all the test cases to use strictly positive weights and values. Would you mind testing some of them out? If we can agree that the test cases are valid, I can update the Coursera thread.

Cheers.

Beau

dgrcode commented

No problem, I'm glad to be of any help 😃

First of all, please note that I cannot be sure that my algorithm is 100% correct. I just know that I've passed both programming assignments, and I think it is correct after checking some edge cases. But I could have missed a bug somewhere.

I've done a loop over your new test cases. You can find below the expected result and the result computed by my algorithm, both with the total capacity, and with the capacity minus one. I stopped when the computation was taking too long already. Results:

  • Testing file: knapsack-example-w-10-n-10-solution-12.txt
    • Expected: 12
    • Computed: 13
    • Computed (C-1): 12
  • Testing file: knapsack-example-w-10-n-10-solution-19.txt
    • Expected: 19
    • Computed: 20
    • Computed (C-1): 19
  • Testing file: knapsack-example-w-10-n-10-solution-22.txt
    • Expected: 22
    • Computed: 22
    • Computed (C-1): 22
  • Testing file: knapsack-example-w-10-n-10-solution-9.txt
    • Expected: 9
    • Computed: 10
    • Computed (C-1): 9
  • Testing file: knapsack-example-w-10-n-100-solution-34.txt
    • Expected: 34
    • Computed: 37
    • Computed (C-1): 34
  • Testing file: knapsack-example-w-10-n-100-solution-36.txt
    • Expected: 36
    • Computed: 38
    • Computed (C-1): 36
  • Testing file: knapsack-example-w-10-n-100-solution-40.txt
    • Expected: 40
    • Computed: 43
    • Computed (C-1): 40
  • Testing file: knapsack-example-w-10-n-100-solution-45.txt
    • Expected: 45
    • Computed: 49
    • Computed (C-1): 45
  • Testing file: knapsack-example-w-100-n-10-solution-150.txt
    • Expected: 150
    • Computed: 154
    • Computed (C-1): 150
  • Testing file: knapsack-example-w-100-n-10-solution-168.txt
    • Expected: 168
    • Computed: 168
    • Computed (C-1): 168
  • Testing file: knapsack-example-w-100-n-10-solution-220.txt
    • Expected: 220
    • Computed: 221
    • Computed (C-1): 220
  • Testing file: knapsack-example-w-100-n-10-solution-95.txt
    • Expected: 95
    • Computed: 95
    • Computed (C-1): 95
  • Testing file: knapsack-example-w-100-n-100-solution-441.txt
    • Expected: 441
    • Computed: 442
    • Computed (C-1): 441
  • Testing file: knapsack-example-w-100-n-100-solution-559.txt
    • Expected: 559
    • Computed: 561
    • Computed (C-1): 559
  • Testing file: knapsack-example-w-100-n-100-solution-576.txt
    • Expected: 576
    • Computed: 576
    • Computed (C-1): 576
  • Testing file: knapsack-example-w-100-n-100-solution-628.txt
    • Expected: 628
    • Computed: 635
    • Computed (C-1): 628
  • Testing file: knapsack-example-w-100-n-1000-solution-1316.txt
    • Expected: 1316
    • Computed: 1324
    • Computed (C-1): 1316
  • Testing file: knapsack-example-w-100-n-1000-solution-1608.txt
    • Expected: 1608
    • Computed: 1618
    • Computed (C-1): 1608
  • Testing file: knapsack-example-w-100-n-1000-solution-1704.txt
    • Expected: 1704
    • Computed: 1714
    • Computed (C-1): 1704
  • Testing file: knapsack-example-w-100-n-1000-solution-1855.txt
    • Expected: 1855
    • Computed: 1864
    • Computed (C-1): 1855
  • Testing file: knapsack-example-w-1000-n-100-solution-4187.txt
    • Expected: 4187
    • Computed: 4187
    • Computed (C-1): 4187
  • Testing file: knapsack-example-w-1000-n-100-solution-4542.txt
    • Expected: 4542
    • Computed: 4542
    • Computed (C-1): 4542
  • Testing file: knapsack-example-w-1000-n-100-solution-5884.txt
    • Expected: 5884
    • Computed: 5884
    • Computed (C-1): 5884
  • Testing file: knapsack-example-w-1000-n-100-solution-7078.txt
    • Expected: 7078
    • Computed: 7078
    • Computed (C-1): 7078
  • Testing file: knapsack-example-w-1000-n-1000-solution-15759.txt
    • Expected: 15759
    • Computed: 15767
    • Computed (C-1): 15759
  • Testing file: knapsack-example-w-1000-n-1000-solution-17973.txt
    • Expected: 17973
    • Computed: 18000
    • Computed (C-1): 17973
  • Testing file: knapsack-example-w-1000-n-1000-solution-19353.txt
    • Expected: 19353
    • Computed: 19372
    • Computed (C-1): 19353
  • Testing file: knapsack-example-w-1000-n-1000-solution-20782.txt
    • Expected: 20782
    • Computed: 20782
    • Computed (C-1): 20782
  • Testing file: knapsack-example-w-10000-n-1000-solution-146537.txt
    • Expected: 146537
    • Computed: 146537
    • Computed (C-1): 146537
  • Testing file: knapsack-example-w-10000-n-1000-solution-166063.txt
    • Expected: 166063
    • Computed: 166063
    • Computed (C-1): 166063
  • Testing file: knapsack-example-w-10000-n-1000-solution-174944.txt
    • Expected: 174944
    • Computed: 174944
    • Computed (C-1): 174944
  • Testing file: knapsack-example-w-10000-n-1000-solution-204439.txt
    • Expected: 204439
    • Computed: 204439
    • Computed (C-1): 204439

As you can see, all your results are the same than my results when I use C-1 as capacity. For example, for the first test case, the result is 13 if you pick the following items:

  • Items in the sack (starting at item 1): [2, 3, 4, 5, 7, 9]
  • Total value in the sack: 13
  • Total weight in the sack: 10

Check if your loop for the capacity is reaching the total capacity. In some programming languages, when you iterate "from 0 to n", the actual values being iterated over are 0, 1, ..., n-1. For example, if you are using python, be aware that range(n) will allow you to iterate from 0 to n-1.

Let me know if I can help you sorting this out! 👍

beaunus commented

Thank you very much for your ideas. I think you were correct about the (c-1) bug.

I used Java to solve this assignment. I had previously used a line solution[size-1] to fix an ArrayIndexOutOfBoundsException. I fixed the code to be solution[size]. Please have a look at the examples here and let me know if you get the same results.

Cheers.
Beau

dgrcode commented

I've checked again and now everything looks great! 👍

This issue can be closed now. Thank you for the fix!