Go: package main

import (
	"bufio"
	"os"
	"strconv"
	"strings"
	"fmt"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	Case := 1
	for {
		scanner.Scan()
		W, _ := strconv.Atoi(scanner.Text())
		if W == 0 {
			break
		}
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		w := make([]int, n+1)
		v := make([]int, n+1)
		for i := 1; i <= n; i++ {
			scanner.Scan()
			info := strings.Split(scanner.Text(), ",")
			v[i], _ = strconv.Atoi(info[0])
			w[i], _ = strconv.Atoi(info[1])
		}
		// fmt.Println(v)
		// fmt.Println(w)
		dp := make([][]int, n+1)
		for i := range dp {
			dp[i] = make([]int, W+1)
		}
		maxV := -(1 << 21)
		minW := 1 << 21
		for i := 1; i <= n; i++ {
			for j := 1; j <= W; j++ {
				// fmt.Println(dp)
				if j-w[i] >= 0 {
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])
					if maxV < dp[i][j] {
						maxV = dp[i][j]
						minW = j
					} else if maxV == dp[i][j] {
						minW = min(minW, j)
					}
				} else {
					dp[i][j] = dp[i-1][j]
				}
			}
		}
		fmt.Printf("Case %d:\n", Case)
		Case += 1
		fmt.Println(maxV)
		fmt.Println(minW)
	}
}
func max(x, y int) int {
	if x < y {
		return y
	}
	return x
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

Python: # -*- coding: utf-8 -*-

import sys
import os
import math
import itertools

case = 1
for s in sys.stdin:
    W = int(s)
    if W == 0:
        break

    N = int(input())
    values = []
    weights = []
    for i in range(N):
        v, w = map(int, input().split(','))
        values.append(v)
        weights.append(w)

    max_value = 0
    max_value_weight = 0
    for use_flags in itertools.product([0, 1], repeat=len(weights)):

        sum_value = 0
        sum_weight = 0
        for i, use_flag in enumerate(use_flags):
            if use_flag == 1:
                sum_value += values[i]
                sum_weight += weights[i]
        if sum_weight <= W and sum_value > max_value:
            max_value = sum_value
            max_value_weight = sum_weight

    print('Case {}:'.format(case))
    case += 1
    print(max_value)
    print(max_value_weight)

Python: # Aizu Problem 0042: A Thief
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def knapsack(n, v, w, W):
    #
    # 0/1 knapsack implementation
    #
    # Input:
    #    Values (stored in array v)
    #    Weights (stored in array w)
    #    Number of distinct items (n)
    #    Knapsack capacity (W)
    #
    m = [[0 for _ in range(W + 1)] for __ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(W + 1):
            if w[i - 1] > j:
                m[i][j] = m[i-1][j]
            else:
                m[i][j] = max(m[i-1][j], m[i-1][j-w[i - 1]] + v[i - 1])
    print(m)
    return m[N][W]

def total_value(items, max_weight):
    return  sum([x[2] for x in items]) if sum([x[1] for x in items]) < max_weight else 0
 
cache = {}
def solve(items, max_weight):
    if not items:
        return ()
    if (items,max_weight) not in cache:
        head = items[0]
        tail = items[1:]
        include = (head,) + solve(tail, max_weight - head[1])
        dont_include = solve(tail, max_weight)
        if total_value(include, max_weight) > total_value(dont_include, max_weight):
            answer = include
        else:
            answer = dont_include
        cache[(items,max_weight)] = answer
    return cache[(items,max_weight)]

case = 0
while True:
    cache = {}
    W = int(input())
    if W == 0:
        break
    N = int(input())
    items = []
    for n in range(N):
        a, b = [int(_) for _ in input().split(',')]
        items.append(("", b, a))
    items = tuple(items)
    solution = solve(items, W)
    case += 1
    print("Case %d:" % case)
    print(total_value(solution, W))
    print(sum([x[1] for x in solution]))

Python: # AOJ 0042 A Thief
# Python3 2018.6.22 bal4u

MAX = 1003

for cno in range(1, 100):
	lim = int(input())
	if lim == 0: break
	print("Case ", cno, ":", sep='')
	N = int(input())
	vw = [(0, 0)]
	for i in range(N):
		v, w = list(map(int, input().split(',')))
		vw.append((v, w))

	V = [[0 for j in range(MAX)] for i in range(2)]
	W = [[0 for j in range(MAX)] for i in range(2)]		
	k1, k2 = 0, 1
	for i in range(1, N+1):
		for j in range(1, lim+1):
			v, w = vw[i]
			if w > j:
				V[k2][j] = V[k1][j]
				W[k2][j] = W[k1][j]
			else:
				d = j - w
				if V[k1][d] + v >= V[k1][j]:
					V[k2][j] = V[k1][d] + v
					W[k2][j] = W[k1][d] + w
				else:
					V[k2][j] = V[k1][j]
					W[k2][j] = W[k1][j]
		k1, k2 = k2, k1
	print(V[k1][lim], W[k1][lim], sep='\n')

Python: l=1
for W in iter(input,'0'):
 W=int(W)
 D=[0,0]*W
 for p in[0]*int(input()):
  v,w=map(int,input().split(','))
  for i in range(W,w-1,-1):D[i]=max(D[i],D[i-w]+v)
 print(f'Case {l}:\n{D[W]}\n{D.index(D[W])}')
 l+=1

Python: """
0-1ナップザック
wi...i個目の重さ
vi...i個目の価値

2次元

dp[i][j]...i個目までの宝で重さjの時の価値の最大
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - wi] + vi)  (wi <= j)
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])                          (wi >  j)


1次元

dp[j]...重さjの時の価値の最大
dp[j] = max(dp[j], dp[j - wi] + vi)  (wi <= j <= w)

wi <= j <= wについて更新(j < wiについては変化が無いため更新不要)
前から更新すると更新した結果を使って更新してしまうため後ろから更新
"""

INF = 10 ** 20

def main():
  case = 0

  while True:
    w = int(input())
    if not w:
      break
  
    case += 1
  
    n = int(input())
  
    dp = [0 for _ in range(w + 1)]
    
    for i in range(1, n + 1):
      vi, wi = map(int, input().split(","))
      for j in range(w, wi - 1, -1):
        dp[j] = max(dp[j], dp[j - wi] + vi)
  
    print("Case " + str(case) + ":")
    print(dp[w])
    print(dp.index(dp[w]))
main()

Python: count = 0

while True:
    count += 1
    W = int(input())
    if W == 0:
        break
    N = int(input())
    value = []
    weight = []
    for i in range(N):
        a, b = map(int, input().split())
        value.append(a)
        weight.append(b)
    dp = [[-float("inf") for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1):
        dp[0][i] = 0
        
    for i in range(N):
        for w in range(W+1):
            if w >= weight[i]:
                dp[i+1][w] = max(dp[i][w-weight[i]]+value[i], dp[i][w])
            else:
                dp[i+1][w] = dp[i][w]
    print("Case {0}:\n{1}\n{2}".format(count, dp[N][W], dp[N].index(dp[N][W])))

Python: # ナップサック問題を python で解く
case = 0
while True:
    case += 1
    w = int(input())
    if w == 0:
        break
    n = int(input())
    item = []
    for i in range(n):
        item.append(tuple(map(int, input().split(","))))

    dp = [ [0 for j in range(w + 1)] for i in range(n + 1) ]
    for i in range(n):
        for j in range(w + 1):
            value  = item[i][0]
            weight = item[i][1]
            # dp[i][j] : 0..i番目の荷物、重さ j 以下の最大の価値
            if j - weight >= 0 and dp[i+1][j - weight] == dp[i][j - weight]:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j - weight] + value)
            else:
                dp[i+1][j] = max(dp[i][j], dp[i+1][j-1])

    for j in range(w + 1):
        if dp[n][j] == dp[n][w]:
            max_w = j
            break

    print("Case {0}:".format(case))
    print(dp[n][w])
    print(max_w)

Python: import itertools

def solve():
    cache = {}
    def loop(i, w):
        if (i, w) in cache:
            return cache[i, w]
        if i == N:
            return (0, 0)
        cache[i, w] = loop(i + 1, w)
        if v[i][1] <= w:
            t = loop(i + 1, w - v[i][1])
            cache[i, w] = max(cache[i, w], (t[0] + v[i][0], t[1] + v[i][1]), key=lambda u: u[0])
        return cache[i, w]
    return loop(0, W)

for dn in itertools.count(1):
    W = int(input())
    if W == 0: break
    N = int(input())
    v = [tuple(map(int, input().split(','))) for _ in range(N)]
    optim = solve()
    print("Case %d:\n%d\n%d" % (dn, optim[0], optim[1]))