Ideone.com

fork download

copy

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#define int long long
using namespace std;
 
#define INF 1e18
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, W;
    int S = 0;
    cin >> N >> W;
    vector<int> w(N), v(N);
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
        S += v[i]; 
    }
    vector<int> dp(S + 1, 1e9); //從價值來dp 
    dp[0] = 0;
    for(int i = 0; i < N; i++){
      for(int j = S; j >= 0; j--){
        if(j >= v[i]){
          dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
        }
      }
    }
    for(int i = 0; i <= S; i++){
      cout << dp[i] << endl; 
    }
    for(int i = S; i >= 0; i--){
      if(dp[i] <= W){
        cout << i << endl;                    
        exit(0);
      }
    }
}

Success #stdin #stdout 0.01s 5300KB

stdin

copy

stdout

copy

https://ideone.com/Bo8om8

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language