Null values in matrix, why?

I'm learning about dynamic programming via the 0-1 knapsack problem.

I'm getting some weird Nulls out from the function part1. Like 3Null, 5Null etc. Why is this?

The code is an implementation of: http://www.youtube.com/watch?v=EH6h7WA7sDw

I use a matrix to store all the values and keeps, dont know how efficient this is since it is a list of lists(indexing O(1)?).

This is my code:

(*  0-1 Knapsack problem
 item = {value, weight} 
  Constraint is maxweight. Objective is to max value. 
 Input on the form:
 Matrix[{value,weight},
       {value,weight},
        ...
      ]
*)

lookup[x_, y_, m_] := m[[x, y]];

part1[items_, maxweight_] := {
  nbrofitems = Dimensions[items][[1]];
  keep = values = Table[0, {j, 0, nbrofitems}, {i, 1, maxweight}];
  For[j = 2, j <= nbrofitems + 1, j++,
    itemweight = items[[j - 1, 2]];
    itemvalue = items[[j - 1, 1]];
    For[i = 1, i <= maxweight, i++,
     {
      x = lookup[j - 1, i, values];
      diff =开发者_运维技巧 i - itemweight;
      If[diff > 0, y = lookup[j - 1, diff, values], y = 0];
      If[itemweight <= i ,
       {If[x < itemvalue + y,
         {values[[j, i]] = itemvalue + y; keep[[j, i]] = 1;},
         {values[[j, i]] = x; keep[[j, i]] = 0;}]
        },
       y(*y eller x?*)]
      }
     ]
    ]
   {values, keep}
  }

solvek[keep_, items_, maxweight_] :=
 {
  (*w=remaining weight in knapsack*)
  (*i=current item*)
  w = maxweight;
  knapsack = {};
  nbrofitems = Dimensions[items][[1]];
  For[i = nbrofitems, i > 0, i--,
   If[keep[[i, w]] == 1, {Append[knapsack, i]; w -= items[[i, 2]]; 
     i -= 1;}, i - 1]];
  knapsack
  }

Clear[keep, v, a, b, c]
maxweight = 5;
nbrofitems = 3;
a = {5, 3};
b = {3, 2};
c = {4, 1};
items = {a, b, c};

MatrixForm[items]

Print["Results:"]
results = part1[items, 5];
keep = results[[1]];
Print["keep:"];
Print[keep];
Print["------"];
results2 = solvek[keep, items, 5];
MatrixForm[results2]
(*MatrixForm[results[[1]]]
MatrixForm[results[[2]]]*)







{{{0,0,0,0,0},{0,0,5 Null,5 Null,5 Null},{0,3 Null,5 Null,5 Null,8 Null},{4 Null,4 Null,7 Null,9 Null,9 Null}},{{0,0,0,0,0},{0,0,Null,Null,Null},{0,Null,0,0,Null},{Null,Null,Null,Null,Null}}}

While your code gives errors here, the Null problem occurs because For[] returns Null. So add a ; at the end of the outermost For statement in part1 (ie, just before {values,keep}.

As I said though, the code snippet gives errors when I run it.

In case my answer isn't clear, here is how the problem occurs:

(
 Do[i, {i, 1, 10}]
  3
 )
(*3 Null*)

while

(
 Do[i, {i, 1, 10}];
 3
 )
(*3*)

The Null error has been reported by acl. There are more errors though.

• Your keep matrix actually contains two matrices. You need to call solvek with the second one: solvek[keep[[2]], items, 5]
• Various errors in solvek:
• i -= 1 and i - 1 are more than superfluous (the latter one is a coding error anyway). The i-- in the beginning of the For is sufficient. As it is now you're decreasing i twice per iteration.
• Append must be AppendTo
• keep[[i, w]] == 1 must be keep[[i + 1, w]] == 1 as the keep matrix has one more row than there are items.
• Not wrong but superfluous: nbrofitems = Dimensions[items][[1]]; nbrofitems is already globally defined

The code of your second part could look like:

solvek[keep_, items_, maxweight_] :=
 Module[{w = maxweight, knapsack = {}, nbrofitems = Dimensions[items][[1]]},
    For[i = nbrofitems, i > 0, i--,
        If[keep[[i + 1, w]] == 1, AppendTo[knapsack, i]; w -= items[[i, 2]]]
    ];
    knapsack
 ]