fork download 
  1. class KnapsackDP
  2.   attr_accessor :s,:n,:mv
  3.   def initialize(s,n)
  4.     @s = s
  5.     @n = n
  6.     initMaxValue()
  7.     @bestValue = search(s,n)
  8.     @bestDiff = (n - @bestValue).abs
  9.     @upperValue = n + @bestDiff
  10.     @lowerValue = n - @bestDiff
  11.     puts "init value=" + @bestValue.to_s + " diff=" + @bestDiff.to_s
  12.   end
  13.   def encodeItemList(s,n)
  14.     return (n.to_s(2)).reverse.each_char.with_index.select {|c,i| c=="1"}.map{|c,i| s[i]}
  15.   end
  16.   def encodeValue(s,n)
  17.     return encodeItemList(s,n).inject(:+)
  18.   end
  19.  
  20.   def search (s,n)
  21.     s.sort!
  22.     if n < (minValue = s.min)
  23.        @bestTrace = [minValue]
  24.        return minValue
  25.     elsif n > (maxValue = s.inject(:+))
  26.        @bestTrace = s
  27.        return maxValue
  28.     else
  29.         left=1
  30.         right=(2** (s.length())) -1
  31.         while left < right do
  32.           mid = (left + right) / 2
  33.           curValue = encodeValue(s,mid)
  34.           if n < curValue
  35.             right = mid - 1
  36.           elsif curValue < n
  37.             left = mid + 1
  38.           else
  39.             @bestTrace = encodeItemList(s,mid)
  40.             return curValue
  41.           end
  42.         end
  43.         curValue1 = encodeValue(s,left)
  44.         curValue2 = encodeValue(s,left+1)
  45.         if (n - curValue1).abs < (curValue2 - n).abs
  46.           @bestTrace = encodeItemList(s,left)
  47.           return curValue1
  48.         else
  49.           @bestTrace = encodeItemList(s,left+1)
  50.           return curValue2
  51.         end
  52.     end
  53.   end
  54.   def initMaxValue()
  55.      @mv = Array.new(@s.length){ Array.new(@s.length, 0)}
  56.      @mv.last[@s.length() - 1] = @s.last
  57.      (@s.length() -2).downto(0) do |i|
  58.         @mv[i][@s.length() - 1] = @s[i] + @s.last
  59.         (@s.length() - 2).downto(i+1) do |j|
  60.           @mv[i][j] = @s[i] + @mv[j][j+1]
  61.         end
  62.         @mv[i][i] = @s[i]
  63.      end
  64. 	   # @mv.each {|d| p d}
  65.   end
  66.   def evalAcc(curAcc,trace)
  67.     curDiff = (n-curAcc).abs
  68.     # p ["evalAcc",curAcc,trace]
  69.     if curDiff < @bestDiff
  70.        @bestValue = curAcc
  71.        @bestDiff = curDiff
  72.        @upperValue = n + @bestDiff
  73.        @lowerValue = n - @bestDiff
  74.        @bestTrace = trace
  75.     end
  76.   end
  77.   def findNear(i,acc,trace)
  78.     # p ["findNear",@s.length,i,acc,trace]
  79.     if (i >= @s.length() -1)
  80.        evalAcc(acc,trace) ## 止めた場合
  81.     #   p "exit at #1"
  82.        return
  83.     elsif (acc ) > @upperValue ## 既に上限を超えた場合
  84.     #   p "exit at #2 acc=" + acc.to_s + " > " + @upperValue.to_s
  85.        return
  86.     else
  87.        findNear(i+2,(acc),trace) 		## s[i]を足さないで、後続の数列を加算
  88.        (i+1).upto(@s.length() -1) do |j|
  89.              if ((acc + @mv[i][j]) >= @lowerValue)  ## まだ下限値を超える見込みの在る値
  90. 	             # p "findNear i=" + i.to_s + " j=" + j.to_s + " " + (trace + [s[j]]).to_s
  91.                findNear(j+1,(acc + @s[j]),trace + [s[j]]) ## s[i]とs[j]を足して、後続の数列を加算
  92.              else 
  93.     #           p "break at #4 acc=" + acc.to_s + " " + "@mv[" + i.to_s + "][" + j.to_s + "]=" + @mv[i][j].to_s + " < " + @lowerValue.to_s
  94.                 break
  95.              end
  96.        end
  97.     end
  98.   end
  99.   def findValue()
  100.      findNear(1,0,[])
  101.      findNear(0,@s[0],[s[0]])
  102.      puts "nearest Value =" + @bestValue.to_s() + " diff=" + @bestDiff.to_s()
  103.      p @bestTrace
  104.      p @bestTrace.inject(:+)
  105.  
  106.      p @s
  107.   end
  108. end
  109. q1=KnapsackDP.new([17,19,23,29],42)
  110. q1.findValue()
Success #stdin #stdout 0.01s 28688KB
comments (?)
stdin 
Standard input is empty
stdout 
init value=46 diff=4
nearest Value =40 diff=2
[17, 23]
40
[17, 19, 23, 29]
https://ideone.com/CE1JjZ
language:
Ruby (ruby 2.5.5)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!