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++
	}
}

C++: #include <bits/stdc++.h>
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
constexpr int INF = 1000000000;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
using namespace std;

using Weight = int;
struct Edge {
  int src, dst;
  Weight weight;
  Edge(const int s = 0, const int d = 0, const Weight w = 0) : src(s), dst(d), weight(w) {}
};

using Edges = std::vector<Edge>;

class Graph {
  std::vector<Edges> g;

public:
  Graph(const int size = 0) : g(size) {}
  size_t size() const { return g.size(); }
  const Edges &operator[](const int i) const { return g[i]; }
  void addArc(const int src, const int dst, const Weight w = 1) { g[src].emplace_back(src, dst, w); }
  void addEdge(const int node1, const int node2, const Weight w = 1) {
    addArc(node1, node2, w);
    addArc(node2, node1, w);
  }
};

vector<Weight> dijkstra(const Graph &g, const int src) {
  using state = pair<Weight, int>;
  priority_queue<state, vector<state>, greater<state>> q;
  vector<Weight> dist(g.size(), INF);
  dist[src] = 0;
  q.emplace(0, src);
  while (q.size()) {
    Weight d;
    int v;
    tie(d, v) = q.top();
    q.pop();
    if (dist[v] < d) continue;
    for (auto &e : g[v]) {
      if (cmin(dist[e.dst], dist[v] + e.weight)) q.emplace(dist[e.dst], e.dst);
    }
  }
  return dist;
}

int main() {
  int caseIndex = 0;
  int W;
  while (cin >> W, W) {
    cout << "Case " << ++caseIndex << ':' << endl;
    int N;
    cin >> N;
    Graph g((N + 1) * (W + 1));
    rep(i, W) g.addArc(i, i + 1, 0);
    rep(i, N) {
      int v, w;
      char gomi;
      cin >> v >> gomi >> w;
      rep(j, W + 1) {
        g.addArc(i * (W + 1) + j, (i + 1) * (W + 1) + j, 0);
        if (j + w <= W) g.addArc(i * (W + 1) + j, (i + 1) * (W + 1) + j + w, -v);
      }
    }
    if (N * W >= 1e5) exit(0);
    vector<Weight> dist = dijkstra(g, 0);
    int maxi = dist.back();
    cout << -maxi << endl;
    rep(i, W + 1) if (maxi == dist[N * (W + 1) + i]) {
      cout << i << endl;
      break;
    }
  }
}

C++: #include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dp[2001][2001];

int main(void)
{
	int w;
	int n;
	int cnt;
	int max;
	
	cnt = 1;
	while (1){
		int value[1000];
		int weight[1000];
		
		scanf("%d", &w);
		
		if (w == 0){
			break;
		}
		
		scanf("%d", &n);
		
		memset(dp, -1, sizeof(dp));
		
		for (int i = 0; i < n; i++){
			scanf("%d,%d", &value[i], &weight[i]);
			dp[i][0] = 0;
		}
		
		for (int i = 1; i <= n; i++){
			for (int j = 0; j <= w; j++){
				if (dp[i - 1][j] != -1 && j + weight[i - 1] <= w){
					dp[i][j + weight[i - 1]] = dp[i - 1][j] + value[i - 1];
				}
				if (dp[i - 1][j] != -1){
					dp[i][j] = dp[i - 1][j];
				}
			}
		}
		
		for (int i = 0; i <= w; i++){
			if (dp[n][i] > dp[n][max]){
				max = i;
			}
		}
		
		printf("Case:%2d\n%d\n%d\n", cnt++, dp[n][max], max);
	}
	
	return (0);
}

C++: #include <stdio.h>

int takara[1024][1024];

int main(void)
{
	int i, j;
	int n;
	int w;
	int t[1024];
	int we[1024];
	int max;
	int c;
	
	c = 0;
	while (scanf("%d", &w), w != 0){
		scanf("%d", &n);
		for (i = 0; i <= n; i++){
			for (j = 0; j <= w; j++){
				takara[i][j] = 0;
			}
		}
		for (i = 0; i < n; i++){
			scanf("%d,%d", &t[i], &we[i]);
		}
		for (i = 0; i < n; i++){
			for (j = 0; j <= w; j++){
				if (takara[i + 1][j] < takara[i][j]){
					takara[i + 1][j] = takara[i][j];
				}
				if (takara[i + 1][j + we[i]] < takara[i][j] + t[i]){
					takara[i + 1][j + we[i]] = takara[i][j] + t[i];
				}
			}
		}
		
//		for (i = 0; i <= n; i++){
//			for (j = 0; j <= w; j++){
//				printf("%4d", takara[i][j]);
//			}
//			printf("\n");
//		}
		max = 0;
		for (i = 0; i <= w; i++){
			if (takara[n][i] > takara[n][max]){
				max = i;
			}
		}
		printf("Case %d:\n%d\n%d\n", c + 1, takara[n][i], max);
		c++;
	}
	return (0);
}

C++: #include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stdio.h>
using namespace std;

class treasure
{
public:
int value, weight;
bool have;
};

treasure tre[1001];
int N,W, VALUE = 0, WEIGHT = 999999;

void calcu()
{
	int sum_v = 0, sum_w = 0;
	for (int i = 0; i < N; i++)
	{
		if (tre[i].have == true)
		{
			sum_v += tre[i].value;
			sum_w += tre[i].weight;
		}
	}
	if (sum_v>VALUE)
	{
		WEIGHT = sum_w;
		VALUE = sum_v;
	}
	else if(sum_v==VALUE &&  WEIGHT>sum_w)
	{
		 WEIGHT = sum_w;
	}
}

void function(int n, int w)//0,W
{
	if (n >= N)	  
	{
		calcu();
	}
	else if (tre[n].weight > w)	 
	{
		tre[n].have=false;
		function(n + 1, w);
	}
	else
	{
		tre[n].have = true;
		function(n + 1, w - tre[n].weight);
		tre[n].have = false;
		function(n + 1, w);
	}
}

int main()
{
	int W;
	for (int count = 1; cin >> W, W != 0; count++)
	{
		VALUE = 0;
		WEIGHT = 999999;
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			scanf("%d,%d", &tre[i].value, &tre[i].weight);
		}
		function(0,W);
		cout << "case " << count << ":" << endl;
		cout << VALUE << endl;
		cout << WEIGHT << endl;
	}
	return 0;
}

C++: # include <iostream>
# include <algorithm>

const int MAX_N = 1001;
const int MAX_W = 1001;

int t;
int n, W;
int v[MAX_N], w[MAX_N];

int dp[MAX_N][MAX_W];

int main() {
	while (1) {
		std::cin >> W;
		if (w == 0)
			break;
		std::cin >> n;
		char ch;
		for (int i = 1; i <= n; ++i)
			std::cin >> v[i] >> ch >> w[i];
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j <= W; ++j)
				dp[i][j] = 0;
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 0; j <= W; ++j) {
				if (w[i] > j)
					continue;
				dp[i][j] = std::max(dp[i - 1][j - w[i]] + v[i], dp[i][j]);
			}
		}
		int max = 0, maxv;
		for (int i = 0; i <= W; ++i) {
			if (max < dp[n][i]) {
				maxv = i;
				max = dp[n][i];
			}
		}
		++t;
		std::cout << "Case " << t << ':' << std::endl;
		std::cout << max << std::endl << maxv << std::endl;
	}
	return 0;
}