fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long MaxN = 1e5 + 5;
  5.  
  6. long long n, W;          // n: số loại đồ vật, W: sức chứa tối đa của balo
  7. long long w[MaxN];        // w[i]: khối lượng của đồ vật i
  8. long long v[MaxN];        // v[i]: giá trị của đồ vật i
  9. long long dp[MaxN];       // dp[j]: giá trị lớn nhất đạt được với sức chứa j
  10.  
  11. int main()
  12. {
  13.     ios_base::sync_with_stdio(0);
  14.     cin.tie(0);
  15.  
  16.     cin >> n >> W;
  17.  
  18.     for(long long i = 1; i <= n; i++)
  19.     {
  20.         cin >> w[i] >> v[i];
  21.     }
  22.  
  23.     for(long long i = 1; i <= n; i++)
  24.     {
  25.         for(long long j = w[i]; j <= W; j++)
  26.         {
  27.             dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
  28.         }
  29.     }
  30.  
  31.     cout << dp[W];
  32. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xk2X9b
language:
C++14 (gcc 8.3)
created:
2 hours ago
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!