Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- int n,capacity;
- std::vector<int>wt,val;
- int dp[2][10001];
- void read(){
- std::cin >> n >> capacity;
- wt.resize(n + 1);
- val.resize(n + 1);
- for(int i = 1;i <= n;i++)
- std::cin >> wt[i] >> val[i];
- }
- void precalc(){
- for(int i = 1;i <= n;i++){
- int index = (i % 2 == 0 ? 0 : 1);
- for(int j = 1;j <= capacity;j++){
- if(index == 0){// if i is an even nr
- if(j < wt[i])
- dp[0][j] = dp[1][j];
- else
- dp[0][j] = std::max(dp[1][j],dp[1][j - wt[i]] + val[i]);
- }else{
- if(j < wt[i])
- dp[1][j] = dp[0][j];
- else
- dp[1][j] = std::max(dp[0][j],dp[0][j - wt[i]] + val[i]);
- }
- }
- }
- }
- void print(){
- if(n % 2 == 0)
- std::cout << dp[0][capacity];
- else
- std::cout << dp[1][capacity];
- }
- int main(){
- read();
- precalc();
- print();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement