矩陣中的空值，爲什麼？

我正在通過0-1揹包問題學習動態編程。矩陣中的空值，爲什麼？

我從函數part1中得到了一些奇怪的空值。像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}}}

來源

2011-09-22 olapola

「;」在If's等結尾的代碼中。改變你的「keep [[j，i]] = 0;」和「」keep [[j，i]] = 1;「上面並移除」;「並看看會發生什麼，因爲這些都是終止表達式，所以最後不需要」;「...嘗試... – Nasser

我認爲如果你使用像'Module'這樣的範圍結構而不是括號{...}，你的代碼將會得到很大的改進。顯式循環通常可以被Mathematica的函數式編程結構（如Map，Apply，FoldList） '等等，從而產生更快更簡潔的代碼。 –

當你的代碼在這裏給出了錯誤，發生Null問題，因爲For[]回報Null。因此，在最外面的For語句的結束part1即只是{values,keep}之前添加;（

正如我雖然說的，代碼段給出了錯誤，當我運行它。

如果我的回答」不是個牛逼清楚，這裏是如何發生的問題：

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

而

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

來源

2011-09-22 10:12:59 acl

你的答案的措詞稍微偏離。它不是「空的問題發生，因爲For []沒有返回值」，因爲For []返回Null（因爲沒有被...抑制），所以問題發生，然後乘以{values，keep}。 –

@Sjoerd這是一個很好的觀點 – acl

的acl報告了錯誤。雖然有更多的錯誤。

您的keep矩陣實際上包含兩個矩陣。你需要調用solvek與第二個：solvek[keep[[2]], items, 5]
各種錯誤在solvek：
i -= 1和i - 1比多餘以上（後者是一個編碼錯誤反正）。在For開頭的i--就足夠了。現在你每次迭代都會減少兩次。
Append必須AppendTo
keep[[i, w]] == 1必須keep[[i + 1, w]] == 1作爲保持矩陣具有多一個排比有物品。
沒有錯，但多餘的：nbrofitems = Dimensions[items][[1]];nbrofitems已經被全局定義

你的第二個部分的代碼可能看起來像：

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 
]

發生這種情況時，我尋找額外

來源

2011-09-22 13:45:15

矩陣中的空值，爲什麼？

回答

相關問題