# encoding:utf-8
# ruby1.9是用ASCII编码来读源码的, http://zires.info/2011/03/17/invalid-multibyte-char-us-ascii-ruby1-9/
class KnapSack
attr_reader :weight, :value
attr_writer :weight, :value
def initialize(weight, value)
@weight = weight
@value = value
end
def to_s
"{weight:#{weight}, value:#{value}}"
end
end
class KnapsackProblem
attr_writer :bags, :total_weight
attr_reader :bags, :total_weight, :best_value, :best_values, :best_solutions
def initialize(bags, total_weight)
@bags = bags
@total_weight = total_weight
@n = bags.length
@best_values = Array.new(@n + 1) { Array.new(@total_weight + 1) }
@best_solutions = Array.new
end
def solve
puts '给定背包:'
bags.each do |bag|
puts bag.to_s
end
puts '给定总称重: ' + @total_weight.to_s
(0..@total_weight).each do |j|
(0..@n).each do |i|
if i == 0 || j == 0
@best_values[i][j] = 0
else
if j < @bags[i - 1].weight
@best_values[i][j] = @best_values[i - 1][j]
else
iweight = @bags[i - 1].weight
ivalue = @bags[i - 1].value
@best_values[i][j] = [@best_values[i - 1][j], ivalue + @best_values[i - 1][j - iweight]].max
end
end
end
end
temp_weight = @total_weight
@n.downto(1).each do |i|
if @best_values[i][temp_weight] > @best_values[i - 1][temp_weight]
@best_solutions.push(@bags[i - 1])
temp_weight -= @bags[i - 1].weight
if temp_weight == 0
break
end
end
@best_value = @best_values[@n][@total_weight]
end
end
end
require "test/unit"
class TestKnapSack < Test::Unit::TestCase
def test_solve
bags = [KnapSack.new(2, 13), KnapSack.new(1, 10), KnapSack.new(3, 24), KnapSack.new(2, 15),
KnapSack.new(4, 28), KnapSack.new(5, 33), KnapSack.new(3, 20), KnapSack.new(1, 8)]
total_weight = 12
kp = KnapsackProblem.new(bags, total_weight)
kp.solve
puts " -------- 该背包问题实例的解: --------- "
puts "最优值:#{kp.best_value}"
puts "最优解【选取的背包】: "
print kp.best_solutions, "\n"
puts "最优值矩阵:"
best_values = kp.best_values
best_values.each do |r|
r.each do |c|
printf("%-5d", c)
end
puts
end
end
end
关于算法解释,可以参看这篇文章:01背包问题动态规划详解
分享到:
相关推荐
0/1背包问题是学习动态规划算法最经典的例子 Java代码实现0/1背包问题 代码里有详细的注释,比较好理解
设计0/1背包问题的动态规划算法,要求输出背包内物品的最大价值以及选入背包的物品种类。利用c语言(c++语言)实现算法,给出程序的正确运行结果。
算法设计实验报告,包括:蛮力、动态规划、回溯、分支限界四种算法求解0/1背包问题的基本思想、时间复杂度分析,C++实现代码,运行结果截图,实验心得。
算法实验中用动态规划法解0-1背包问题,这里提供了源代码,仅供参考
0/1背包问题优先队列式分支界限算法c++实现
利用回溯算法解决0/1背包问题。类knapsack为背包类,bound是上界函数,函数bknapsack实现0/1背包回溯算法。内有详细注释。
0/1背包问题动态规划算法 一维数组实现 测试结果: 0 4 5 9 10 11 15 15 17 18 19 23 23 包负重为12时最优结果值为:23 包负重为1时最优结果物品组成:[w:1 v:4] 包负重为2时最优结果物品组成:[w:2 v:5] 包负重为3时...
算法课程设计 背包问题 0/1背包问题 实现算法课程设计 背包问题 0/1背包问题 实现 算法课程设计 背包问题 0/1背包问题 实现算法课程设计 背包问题 0/1背包问题 实现 算法课程设计 背包问题 0/1背包问题 实现 算法...
C++语言描述,VC++6。0下运行,用动态规划法求解0/1背包问题,代码里现有很详细的注释,是学习算法的很好参考。
0/1背包问题相关算法,有几个不同的算法,都是解决0/1背包问题的相关算法
0-1背包问题 动态规划 分支限界 回溯 贪心四种方法
利用动态规划算法解决0/1背包问题 自己设定背包容量、物品数量、以及各物品的重量和价值,测试结果是否为最优方案。
采用优先队列式分枝限界法求解0/1背包问题,算法设计第五章,描述的很清晰,里面有完整代码,由于害怕你弄混,所以完整运行的代码参考我的博客文章即可
实验二 用动态规划法求解0/1背包问题 实验三 用贪心算法求解Prim算法 实验四 用回溯法求解N后问题 实验五 用分支限界法实现旅行售货员问题 这些实验的大部分源代码都是书上的, 我用的是WindowsXP SP2 VisualC++6.0...
0/1 算法 分析 设计 实现 背包问题,c语言实现
0-1背包问题动态规划详解及代码,下载使用,0-1背包问题动态规划详解及代码。
基于MATLAB平台,用动态规划法解决0-1背包问题,较为简单。参数分别为[物品重量,物品价值,背包容量,背包价值]
实验目标实验目标: (1)掌握用动态规划方法求解实际问题的基本思路。 (2)进一步理解动态规划方法的实质,巩固设计动态规划算法的基本步骤。 实验任务: ...(1) 实现0-1背包问题的动态规划算法
C# 0/1背包问题 过程演示 源码。比较简单,但是网上在此之前好像没出现过。
背包的重量有限,每次只可取一种商品。利用动态规划实现所选商品总价值的最大值。