napzack.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;
#define MAX_N        100
#define MAX_V        100
#define INF (1<<21)
int main(){
  int w[MAX_N], v[MAX_N];
  int n, W;
  int dp[MAX_N+1][MAX_N*MAX_V+1];
  while(1) {
    cin >> n >> W;
    if(!(n && W)) break;
 // dp[i][j]...i番目までの品物を価値j以下になるよう詰めたときの重さの最小値

    for(int i = 0; i < n; i++){
      cin >> w[i] >> v[i];
      for(int j = 0; j < MAX_N*MAX_V+1; j++){ 
	dp[i][j] = INF;
      }
    }
    dp[0][0] = 0;		
    for(int i = 0; i < n+1; i++) {    
      for(int j = 0; j < MAX_N*MAX_V+1; j++) {
	dp[i+1][j] = min(dp[i][j], dp[i][j-v[i]]+w[i]);  
      }   
    }
    int res;
    for(int i = 0; i < MAX_N*MAX_V+1; i++) {
      if(dp[n][i] <= W) {
	res = i;
     }
    }
    cout << res << endl;
  }
}