inage · December 7, 2013 14:52
diff --git a/unlimited_knapsack.rb b/unlimited_knapsack.rb
 ## 個数制限なしナップサック問題
 ## http://rubyfiddle.com/riddles/9eb7a

 n = 3
 w = [3,4,2]
 v = [4,5,3]
 W = 7

 dp = Array.new(W+1,0)
 i=j=0

 n.times{|i|
    j = w[i]
  while j <= W
    dp[j] = [dp[j],dp[j-w[i]]+v[i]].max
    j+=1
  end
  }
 print dp[W]
	## 個数制限なしナップサック問題
	## http://rubyfiddle.com/riddles/9eb7a

	n = 3
	w = [3,4,2]
	v = [4,5,3]
	W = 7

	dp = Array.new(W+1,0)
	i=j=0

	n.times{\|i\|
	j = w[i]
	while j <= W
	dp[j] = [dp[j],dp[j-w[i]]+v[i]].max
	j+=1
	end
	}
	print dp[W]
No results found