Emiliatan

Knapsack Problem

Feb 28th, 2019
210
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.50 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #define max(x,y) ((x)>(y)?(x):(y))
  4.  
  5. using namespace std;
  6.  
  7. int pack[10001], wi[101], v[101], n, taget;
  8.  
  9. int main()
  10. {
  11.     scanf("%d", &n);
  12.     memset(pack, 0, sizeof(pack));
  13.     for(int i = 1; i <= n && scanf("%d %d", &wi[i], &v[i]); i++);
  14.  
  15.     scanf("%d", &taget);
  16.     for(int i = 1; i <= n; i++)
  17.         for(int j = taget; j >= wi[i]; j--)
  18.             pack[j] = max(pack[j - wi[i]] + v[i], pack[j]);
  19.  
  20.     printf("%d\n", pack[taget]);
  21.  
  22.     return 0;
  23. }
Advertisement
Add Comment
Please, Sign In to add comment