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 <cstring>
#include <vector>
using namespace std;

int main()
{
	int w, n, i, j, cs, val[1001], wg[1001], dp[1001], inserted[1001];
	cs = 1;
	
	while( cin >> w , w)
	{
		memset( dp, 0, sizeof(dp));
		memset( val, 0, sizeof(val));
		memset( wg, 0, sizeof(wg));
		memset( inserted, 0, sizeof(inserted));
		
		inserted[0] = 1;
		
		cin >> n;
		
		for( i = 1; i <= n; i++)
		{	
			char c;
			cin >> val[i] >> c >> wg[i];
		}
		
		
		for( j = 1; j <= n; j++)
		{
			for( i = 0; i <= w; i++)
				if( inserted[i] && i+wg[j] <= w && dp[i+wg[j]] < dp[i] + val[j] )
				{
						dp[i+wg[j]] = max( dp[i] + val[j], dp[i+wg[j]] );
						inserted[i+wg[j]] = 1;
						i = (i+wg[j]) + 1;
				}
		}
			
		
		for( i = w; i >= 0; i--)
		{
			if( dp[i] > dp[i-1] || i == 0)
			{
				cout << "Case " << cs << ":" << endl;
				cout << dp[i] << endl;
				cout << i << endl;
				cs++;
				break;
			}
		}

	}
	
	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[1000];
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<bits/stdc++.h>
using namespace std;
int dp[1001][1001],wait[1001],value[1001],dpp[1001][50000];
void Initialization()
{
    for(int i=0;i<1001;i++)for(int j=0;j<1001;j++)dp[i][j]=-1;
    for(int i=0;i<1001;i++)for(int j=0;j<50000;j++)dpp[i][j]=-1;
}
int power(int n)
{
    int num=1;
    for(int i=1;i<=n;i++)num*=10;
    return num;
}
int serch(int i,int j,int n)
{
    int num;
    if(dp[i][j]>-1)return dp[i][j];
    else if(i==n)num=0;
    else if(j<wait[i])num=serch(i+1,j,n);
    else num=max(serch(i+1,j,n),serch(i+1,j-wait[i],n)+value[i]);
    return dp[i][j]=num;
}
int wserch(int i,int va,int ser,int n,int w)
{
    int num;
    if(dpp[i][va]>-1)return dpp[i][va];
    else if(i==n)num=w;
    else if(ser<va+value[i])num=wserch(i+1,va,ser,n,w);
    else if(ser==va+value[i])num=wait[i];
    else num=min(wserch(i+1,va,ser,n,w),wserch(i+1,va+value[i],ser,n,w)+wait[i]);
    return dpp[i][va]=num;
}
int main()
{
    int n,w,point,num=1,wai,wa;
    string str;
    while(cin>>w&&w!=0){
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>str;
            value[i]=0;wait[i]=0;
            for(int j=0;;j++){
                if(str[j]==','){
                    for(int k=0;k<j;k++)value[i]+=power(j-k-1)*(str[k]-'0');
                    point=j;
                }
                if(str[j]=='\0'){
                    for(int k=point+1;k<j;k++)wait[i]+=power(j-k-1)*(str[k]-'0');
                    break;
                }
            }
        }
        Initialization();
        point=serch(0,w,n);
        wai=w;
        for(int i=0;i<n;i++){
            if(value[i]<point){
                wa=wserch(i+1,value[i],point,n,w)+wait[i];
                if(wa<wai)wai=wa;
            }
            else if(value[i]==point&&wai>wait[i])wai=wait[i];
        }
        cout<<"Case "<<num<<":\n"<<point<<endl<<wai<<endl;
        num++;
    }
}

C++: #include<stdio.h>
int a,s,d[1001],f[1001],g[1001][1001],h,z,i,j,x;
int main(void)
{
	x=0;
	scanf("%d",&a);
	while(a!=0){
		x++;
		scanf("%d",&s);
		for(i=0;i<s;i++){
			scanf("%d,%d",&d[i],&f[i]);
		}
		for(i=0;i<=s;i++){
			for(j=0;j<=a;j++){
				g[i][j]=0;
			}
		}
		for(i=0;i<=s;i++){
			for(j=0;j<=a;j++){
				if(g[i+1][j+f[i]]<g[i][j]+d[i]&&j+f[i]<=a){
					g[i+1][j+f[i]]=g[i][j]+d[i];
				}
				if(g[i+1][j]<g[i][j]){
					g[i+1][j]=g[i][j];
				}
			}
		}
	/*	for(i=0;i<=s;i++){
			for(j=0;j<=a;j++){
				printf("%d ",g[i][j]);
			}
			printf("\n");
		}*/
		h=0;
		z=0;
		for(i=0;i<=a;i++){
			if(h<g[s][i]){
				h=g[s][i];
				z=i;
			}
		}
		printf("Case %d\n",x);
		printf("%d\n%d\n",h,z);
		scanf("%d",&a);
	}

	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

int dp[1024];

int main(){
    int W, N;
    int n = 0;
    while(scanf("%d", &W), W){
        n++;
        scanf("%d", &N);

        int v, w;
        for (int i = 0; i < N; i++){
            scanf("%d,%d", &v, &w);

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

        int pos = 0;
        for (int i = 1; i <= W; i++){
            if (dp[pos] < dp[i]){
                pos = i;
            }
        }

        printf("Case %d:\n", n);
        printf("%d\n", dp[pos]);
        printf("%d\n", pos);
    }
}

C++: #include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define SIZE(x) ((int)(x).size())
#define UQ(v) v.erase(unique(v,begin(),v,end()),v.end());
#define INF 11922960 
#define pb push_back 
int dxy4[5] = { 0,1,0,-1,0 };
int dxy8[9] = { 0,1,1,0,-1,1,-1,-1,0 };
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)




//vector< vector<int> > v (max1, vector<int>(max2) );
int main() {
	int n, W, count = 0;
	while (1) {
		count++;
		cin >> W >> n;
		if (!W) break;
		vector<vector<int>>dp(n+1000, vector<int>(W+10, 0));
		vector<int> v(n + 1, 0);
		vector<int> w(n + 1, 0);


		 char s;
		rep(i, n) { cin >> v[i+1]>> s>>w[i+1]; }

		rep(i, (n+1)) {
			if (!i)continue;
			//cout << i << "-------" << endl;
			rep(j, W-w[i]+1) {
				dp[i][w[i] + j] = max({ dp[i - 1][w[i] + j], dp[i - 1][j] + v[i]});
				//cout << dp[i][w[i]+j] << " ";
			}
			cout << endl;
		}
		int umax = dp[n][W];
		rep(i, W + 1) {
			if (dp[n][i] == umax) {
				cout << "Case: " << count << endl<< umax << endl << i << endl;
				break;
			}
		}
	}
int jk;
cin >> jk;
	return 0;
}