矩阵中的空值,为什么？

Question

我正在通过0-1背包问题学习动态编程.

我从函数part1中得到了一些奇怪的Null.像3Null,5Null等.为什么会这样？

该代码是以下内容的实现:http: //www.youtube.com/watch？v = EH6h7WA7sDw

我使用矩阵来存储所有值并保持,不知道这是多么有效,因为它是一个列表列表(索引O(1)？).

这是我的代码:

(*  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}}}

Answer 1

虽然您的代码在此处Null出现错误,但问题出现是因为For[]返回Null.因此;,在最外层For语句的末尾添加一个part1(即,就在之前{values,keep}.

正如我所说,代码片段在运行时会出错.

如果我的答案不明确,以下是问题的发生方式:

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

而

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