r - 具有递归函数的 R 中的 KnapSack 动态规划

Question

我在 R 中创建了这个简单的代码来解决具有递归函数的背包程序

n <- c(0,1,2,3,4)
v <- c(10,40,30,50)
w <- c(5,4,6,3)
k <- 10


myfunction  <- function(n,k){
  if (n==0 | k==0){
  output <- 0
  } else if (w[i] > k) {
        output <- myfunction[i-1,w]
  } else {
        output <- max(v[i]+ myfunction(i-1, k-w[i]),myfunction(i-1,k))
      }
return(myfunction)
}

但是，我没有得到作为输出的值，而是整个函数。例如，如果我输入:
我的功能(4,10)

我没有得到 90 的值，但是整个函数都打出来了。



这些是值(value)观

Answer 1

除了@etienne 指出的错误之外，还有几个错误。这是一个带注释的调试 session 。首先我们修复返回的对象:

> myfunction  <- function(n,k){
+   if (n==0 | k==0){
+   output <- 0
+   } else if (w[i] > k) {
+         output <- myfunction[i-1,w]
+   } else {
+         output <- max(v[i]+ myfunction(i-1, k-w[i]),myfunction(i-1,k))
+       }
+ return(output)
+ }
> myfunction(4,10)
Error in if (w[i] > k) { : argument is of length zero

显然 w 和 k 的长度都不为零，这表明它必须是 i . (正如艾蒂安也指出的那样)。查看您的代码，您似乎真的打算i是在满足终止条件之前下降的索引。所以更换n来自 i在它出现的少数情况下:

> myfunction  <- function(i,k){
+   if (i==0 | k==0){
+   output <- 0
+   } else if (w[i] > k) {
+         output <- myfunction[i-1,w]
+   } else {
+         output <- max(v[i]+ myfunction(i-1, k-w[i]),myfunction(i-1,k))
+       }
+ return(output)
+ }
> myfunction(4,10)
Error in myfunction[i - 1, w] : 
  object of type 'closure' is not subsettable

因此，您还犯了在需要括号(即世界非美国地区的括号)的地方使用方括号的错误:

> myfunction  <- function(i,k){
+   if (i==0 | k==0){
+   output <- 0
+   } else if (w[i] > k) {
+         output <- myfunction(i-1,w)
+   } else {
+         output <- max(v[i]+ myfunction(i-1, k-w[i]),myfunction(i-1,k))
+       }
+ return(output)
+ }
> myfunction(4,10)
[1] 90

成功，几乎。大多数警告是因为您使用了 |而不是 ||在条件之一中:

Warning messages:
1: In if (i == 0 | k == 0) { :
  the condition has length > 1 and only the first element will be used
2: In if (w[i] > k) { :
  the condition has length > 1 and only the first element will be used
3: In if (i == 0 | k == 0) { :
  the condition has length > 1 and only the first element will be used
4: In if (i == 0 | k == 0) { :
  the condition has length > 1 and only the first element will be used
5: In if (i == 0 | k == 0) { :
  the condition has length > 1 and only the first element will be used
6: In if (i == 0 | k == 0) { :
  the condition has length > 1 and only the first element will be used

因此，用逻辑 || 替换该实例.要处理似乎没有破坏您的逻辑的其他警告，请意识到 w[i]当 i == 0 时长度为 0 ，因此在首先测试该可能性的条件中添加一个逻辑子句并使用正确的“双与符号”( && ):

myfunction  <- function(i,k){
  if (i==0 || k==0){
  output <- 0
  } else if (length( w[i]) && w[i] > k) {
        output <- myfunction(i-1,w)
  } else {
        output <- max(v[i]+ myfunction(i-1, k-w[i]), myfunction(i-1,k))
      }
return(output)
}

现在你得到:

> myfunction(4,10)
[1] 90