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
}

C++: #include <iostream>
#include <vector>
#include <stdio.h>

using namespace std;

int MAX = 1000*1000;

void solve(int n, int W, vector<int> v, vector<int> w) {
	int **dp = new int*[n];
	for (int i=0; i<n; i++) {
		dp[i] = new int[MAX+1];
		for (int j=0; j<MAX+1; j++)
			dp[i][j] = 0;
	}

	dp[0][w[0]] = v[0];
	for (int i=1; i<n; i++) {
		for (int j = 0; j<MAX+1; j++) {
			dp[i][j] = max(dp[i][j], dp[i-1][j]);
			if (j+w[i] <= W) dp[i][j+w[i]] = max(dp[i][j+w[i]], dp[i-1][j]+v[i]);
		}
	}

	int val = -1, weight = 0;
	for (int j=0; j<=W; j++) {
		if (val < dp[n-1][j]) {
			val = dp[n-1][j];
			weight = j;
		}
	}

	cout << val << endl << weight << endl;

	for (int i=0; i<n; i++)
		delete [] dp[i];
	delete [] dp;
}

int main() {
	

	int n, W;
	int ver = 1;

	cin >> W;
	while (W!=0) {
		cin >> n;

		vector<int> v(n), w(n);
		for (int i=0; i<n; i++)
			scanf("%d,%d", &v[i], &w[i]);

		cout << "Case " << ver << ":" << endl;
		solve(n, W, v, w);

		cin >> W;
		ver++;
	}

	return 0;
}

C++: #include <cstdio>
#include <cstring>
#define max(a,b) a>b?a:b
#define N_MAX 1000
int main() {
    int w, n, cnt = 1;
    int val[N_MAX],g[N_MAX],dp[N_MAX+1];

    while (scanf("%d%d", &w, &n), w){
        for (int i = 0; i < n; i++) {
            scanf("%d,%d", val+i, g+i);
        }
        memset(dp, -1, sizeof(dp));
        dp[0] = 0;
        for (int i = 0; i < n; i++){
            for (int j = w-g[i]; j>= 0; j--)
                if (dp[j]>=0) dp[j+g[i]] = max(dp[j+g[i]], dp[j]+val[i]);
        }
        int p = 0, q = 0;
        for (int i = 0; i <= w; i++) {
            if (dp[i]>p) {
                p = dp[i];
                q = i;
            }
        }

        printf("Case %d:\n%d\n%d\n", cnt++, p, q);
    }
    return 0;
}

C++: #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int w, n, cnt;
int a[1111], b[1111];
int dp[11111];

int main(){

  while(cin >> w, w){
    cin >> n;
    
    for(int i=0;i<n;i++) scanf("%d,%d", &a[i], &b[i]);

    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)
      for(int j=w;j>=0;j--)
	dp[j+b[i]] = max(dp[j]+a[i], dp[j+b[i]]);
    
    int ans = 0;
    for(int i=0;i<=w;i++)
      if(dp[i] > dp[ans]) ans = i;
    
    printf("Case %d:\n%d\n%d", ++cnt, dp[ans], ans);
  }

}

C++: #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int data[1001][2];
int dp[1001][1001];
int n,w;

int solve(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=w;j++){
			if(j >= data[i][1]){
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-data[i][1]]+data[i][0]);
			}else{
				dp[i][j] =dp[i-1][j];
			}
		}
	}
	return dp[n][w];
}

int solve2(){
	for(int i=0;i<=w;i++){
		if(dp[n][w] == dp[n][i]){
			return i;
		}
	}
	return w;
}

int main(){
	int casecount = 0;
	while(true){
		casecount++;
		cin>>w;
		if(w == 0){
			break;
		}
		memset(dp,0,sizeof(dp));

		cin >> n;
		for(int i=1;i<=n;i++){
			scanf("%d,%d",&data[i][0],&data[i][1]);
		}
		
		cout << "Case " << casecount << ":" << endl;
		cout << solve() << endl;
		cout << solve2() << endl;
	}
}

C++: #include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include<cstdlib>


#define INF (1<<21)
#define swap(a,b) {a=a+b; b=a-b; a=a-b;}
#define abs(a) (a > 0 ? a:-a)
#define min(a,b) {a > b ? b:a}
#define max(a,b) {a > b ? a:b}
using namespace std;

//O(W*N)??§??????
#define MAX_W 1000
#define MAX_N 100
#define MAX_VALUE 10000
#define MAX_WEIGHT 1000

int dp[MAX_W+1];
vector<pair<int, int> > Item;
void q42() {
	int W, N;
	int cnt = 1;
	for (; cin >> W;) {
		if (!W) break;

		cin >> N;
		for (int i = 0; i < N; i++) {
			int value, weight;
			char tmp;
			cin >> value >> tmp >> weight;
			Item.push_back(make_pair(value, weight));
		}
		for (int i = 0; i <= W; i++) {
			dp[i] = -1;
		}
		dp[0] = 0;

		for (int i = 0; i < N; i++) {
			int value = Item[i].first;
			int weight = Item[i].second;
			for (int j = W; j >= 0; j--) {
				if (j - weight < 0) continue;
				if (dp[j - weight] == -1) continue;
				dp[j] = max(dp[j], dp[j - weight] + value);
			}
		}

		int ans_value = 0, ans_weight = 0;
		for (int i = 0; i <= W; i++) {
			if (ans_value > dp[i]) {
				ans_value = dp[i];
				ans_weight = i;
			}
		}

		cout << "Case " << cnt << ":" << endl;
		cout << ans_value << endl;
		cout << ans_weight << endl;
		cnt++;
	}
}

int main() {
	q42();
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

typedef pair<int, int> obj;

int main(){
  int N, W, weight, value;
  char ch;
  int case_num = 1;

  while(1){
    cin >> W;
    if(W == 0) break;
    cin >> N;

    //printf("W = %d N = %d\n", W, N);

    vector<obj> obj_list;
    int dp[2][1010];
    memset(dp, -1, sizeof(dp));
    
    for(int i = 0; i < N; i++){
      cin >> value >> ch >> weight;
      obj_list.push_back(obj(value, weight));
      //printf("value = %d weight = %d\n", value, weight);
    }

    dp[0][0] = 0;
    dp[1][0] = 0;

    for(int i = 0; i < N; i++){
      obj o = obj_list[i];

      for(int j = 0; j <= W; j++){
        if(dp[(i+1)%2][j] != -1 && j + o.second <= W){
          dp[i%2][j+o.second] = max(dp[i%2][j+o.second], dp[(i+1)%2][j] + o.first);
        }
      }
    }
    int answer = 0;
    int answer_weight = 0;

    for(int i = 0; i <= W; i++){
      if(answer < dp[(N+1)%2][i]){
        answer = dp[(N+1)%2][i];
        answer_weight = i;
      }
    }

    cout << "Case " << case_num << ":" << endl;
    cout << answer << endl;
    cout << answer_weight << endl;

    case_num++;
  }

  return 0;
}

C++: #include<stdlib.h>
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
void vmax(int,int,int[],int[]);
int sum_w[1001][1001];
int sum_v[1001][1001];
int main(){
	int count=0;
	while(1){
		int i,j,lim=0,N=0,v[1001],w[1001],k=0,l=0;
		for(i=0;i<1001;i++){
			for(j=0;j<1001;j++){
				sum_v[i][j]=0;
				sum_w[i][j]=0;
			}
		}
		count++;
		cin>>lim;
		if(lim==0)break;
		cin>>N;
		for(i=0;i<N;i++){
			scanf("%d,%d",&v[i],&w[i]);
		}
		for(i=0;i<N;i++){
			for(j=0;j<=lim;j++){
				vmax(i,j,v,w);
			}
		}
		for(i=0;i<N;i++){
			if(k<sum_v[N-1][i]){
				k=sum_v[N-1][i];
				l=i;
			}
		}
		cout<<"Case"<<count<<endl;
		cout<<sum_v[N-1][l]<<endl;
		cout<<sum_w[N-1][l]<<endl;

	}
	
	return 0;
}
void vmax(int i,int j,int v[],int w[]){
	if(sum_v[i-1][j]<sum_v[i-1][j-w[i]]+v[i]){
		sum_v[i][j]=sum_v[i-1][j-w[i]]+v[i];
		sum_w[i][j]=sum_w[i-1][j-w[i]]+w[i];
	}
}