Go: package main

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

const MaxW = 1000
const MaxN = 1000

type Tuple struct {
	Value  int
	Weight int
}

func nextLine(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

func solve(w int, n int, vws []Tuple) Tuple {
	var dp [MaxN + 1][MaxW + 1]int

	for i := 0; i < n; i++ {
		for j:= w; j > 0; j-- {
			if j < vws[i].Weight {
				dp[i + 1][j] = dp[i][j]
			} else {
				dp[i + 1][j] = int(math.Max(float64(dp[i][j]), float64(dp[i][j - vws[i].Weight] + vws[i].Value)))
			}
		}
	}

	maxValue := dp[n][w]
	minWeight := w

	for j := w - 1; j > 0; j-- {
		if maxValue == dp[n][j] {
			minWeight = j
		} else {
			break
		}
	}

	return Tuple{Value: maxValue, Weight: minWeight}
}

func main() {
	var sc = bufio.NewScanner(os.Stdin)
	index := 1
	for {
		var w, n int
		w, _ = strconv.Atoi(nextLine(sc))
		if w == 0 {
			return
		}
		n, _ = strconv.Atoi(nextLine(sc))

		vws := make([]Tuple, n, n)
		for i := 0; i < n; i++ {
			array := strings.Split(nextLine(sc), ",")
			v, _ := strconv.Atoi(array[0])
			w, _ := strconv.Atoi(array[1])
			vws[i] = Tuple{Value: v, Weight: w}
		}

		t := solve(w, n, vws)
		fmt.Printf("Case %d:\n", index)
		fmt.Println(t.Value)
		fmt.Println(t.Weight)
		index++
	}
}

Python: case = 0
while True:
    W = int(input())
    if W == 0:
        break
    N = int(input())
    case += 1
    # a list of [itemValue, itemWeight]
    items = [list(map(int,input().split(','))) for i in range(N)]
    dp = {}
    def bestVW(item, capa):
        if (item,capa) in dp:
            return dp[(item,capa)]
        elif item == 0:
            bestVWForCapa = items[item] if items[item][1] <= capa else [0,0]
            dp[(item,capa)] = bestVWForCapa
            return bestVWForCapa
        else:
            if items[item][1] > capa:
                bestVWForCapa = bestVW(item-1, capa)
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
            else:
                pickedVW = bestVW(item-1,capa)
                notPickedVW = list(map(sum, zip(items[item], bestVW(item-1, capa-items[item][1]))))
                bestVWForCapa = pickedVW if pickedVW[0] > notPickedVW[0] else notPickedVW 
                dp[(item,capa)] = bestVWForCapa
                return bestVWForCapa
    msg = "Case "+str(case)+":"
    print(msg)
    print('\n'.join(map(str,bestVW(N-1,W))))

Python: caseN = 0
while True:
    caseN += 1
    W = int(input())
    if W == 0: break
    N = int(input())
    tr = [list(map(int, input().split(','))) for _ in range(N)]
    dp = [0 for x in range(W+1)]
    for x in range(N):
        for y in range(W,tr[x][1]-1,-1):
            dp[y] = max(dp[y], dp[y-tr[x][1]] + tr[x][0])
    sum_weight = 0
    sum_value = 0
    ind = N%2
    for x in range(W+1):
        if dp[x] > sum_value:
            sum_weight = x
            sum_value = dp[x]
    print("Case ", caseN, ":", sep='')
    print(sum_value)
    print(sum_weight)

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()