当前位置: 动力学知识库 > 问答 > 编程问答 >

algorithm - ArrayIndexOutofBoundsException in Knapsack Scala

问题描述:

I am trying to solve Knapsack problem in Scala using dynamic programming .As a part of requirement I also need to show which items are picked to be filled in Knapsack.But I am getting "ArrayIndexOutOfBoundException".

And so far what I have code is like :

availableMoney is equivalent to weight of knapsack.products.channels is equivalent to value[] in knapsack.products.price is equivalent to weight[] in knapsack.

def knapSack(availableMoney: Int, products: List[Product]) : Int = {

var wt = List[Int](products.length)

var value = List[Int](products.length)

for (product <- products) {

value ::= product.channels.length

wt ::= product.price

}

val matrix = Array.fill(2, 2)(0)

val picks = Array.fill(2, 2)(0)

for (i <- 1 to products.length){

for (j <- 0 to availableMoney){

if (wt(i-1)<=j){

matrix(i)(j) = max(matrix(i-1)(j),value(i-1)+matrix(i-1)(j-wt(i-1)));

if (value(i-1)+matrix(i-1)(j-wt(i-1))>matrix(i-1)(j))

picks(i)(j)= 1;

else

picks(i)(j)= -1;

}

else{

picks(i)(j) = -1;

matrix(i)(j) = matrix(i-1)(j);

}

}

}

matrix(products.length)(availableMoney)

}

网友答案:

There are a couple of issues I think:

  • j runs from 0 to availableMoney, and is then used as an index into picks and matrix which have been initialised to specific sizes, so if availableMoney exceeds those dimensions, it will fail
  • i runs from 1 to products.length but is also used as an index into picks and matrix, so will miss 0 and if there are more products than the second dimension size, it will fail

Use some println debugging to check more closely what is going on. Looks like an interesting algorithm. Post us a solution once you get it working :)

分享给朋友:
您可能感兴趣的文章:
随机阅读: