Submission #608222

---

Source Code Expand

P = Struct.new(:v, :w)

N, W = gets.split.map(&:to_i)
List = []
N.times{
	List.push P.new(*gets.split.map(&:to_i))
}

def solve1
	def solve(i, val, rest_w)
		if i == List.size
			val
		elsif List[i].w > rest_w
			solve i+1, val, rest_w
		else
			[solve(i+1, val+List[i].v, rest_w-List[i].w), solve(i+1, val, rest_w)].max
		end
	end
	puts solve(0, 0, W)
end

def solve2
	a = Array.new(W+1, 0)
	b = Array.new(W+1, 0)
	(N-1).downto(0){|i|
		(W+1).times{|j|
			if j < List[i].w
				a[j] = b[j]
			else
				a[j] = [b[j], b[j-List[i].w] + List[i].v].max
			end
		}
		b = a
		a = Array.new(W+1, 0)
	}
	puts b[W]
end

def solve3
	$memo = Array.new(N+1){ {} }
	def solve(i, val, rest_w)
		if $memo[i][val] && $memo[i][val] > rest_w
			rest_w
		else
			$memo[i][val] = if i == List.size
				rest_w
			elsif List[i].w > rest_w
				solve i+1, val, rest_w
			else
				[solve(i+1, val+List[i].v, rest_w-List[i].w), solve(i+1, val, rest_w)].max
			end
		end
	end
	solve 0, 0, W
	puts $memo[N].keys.max
end

if List.map(&:w).max <= 1000
	solve2
elsif List.map(&:v).max <= 1000
	solve3
else
	solve1
end

Submission Info

Judge Result