Niloy007

In Class Assignment On DP

May 5th, 2021
484
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. char name[1000];
  4. int w[1000], v[1000];
  5.  
  6. void Knapsack(int w[], int v[], int n, int W) {
  7.     int P[n + 1][W + 1];
  8.     for (int w = 0; w <= W; w++) {
  9.         P[0][w] = 0;
  10.     }
  11.  
  12.     for (int i = 0; i <= n; i++) {
  13.         P[i][0] = 0;
  14.         if (i == 0) {
  15.             continue;
  16.         }
  17.         int wi = w[i - 1];
  18.         int vi = v[i - 1];
  19.         for (int w = 1; w <= W; w++) {
  20.             if (wi <= w) {
  21.                 if (vi + P[i - 1][w - wi] > P[i - 1][w]) {
  22.                     P[i][w] = vi + P[i - 1][w - wi];
  23.                 } else {
  24.                     P[i][w] = P[i - 1][w];
  25.                 }
  26.             } else {
  27.                 P[i][w] = P[i - 1][w];
  28.             }
  29.         }
  30.     }
  31.    
  32.     cout << P[n][W] << endl;
  33.     int res = P[n][W];
  34.     int a = W;
  35.     for (int i = n; i > 0 && res > 0; i--) {
  36.         if (res == P[i - 1][a])
  37.             continue;      
  38.         else {
  39.             cout << name[i - 1] << endl;
  40.             res = res - v[i - 1];
  41.             a = a - w[i - 1];
  42.         }
  43.     }
  44. }
  45.  
  46. int main() {
  47.     int c, n;
  48.     cin >> c >> n;
  49.    
  50.     for (int i = 0; i < n; i++) {
  51.         cin >> name[i] >> w[i] >> v[i];
  52.     }
  53.     Knapsack(w, v, n, c);
  54. }
RAW Paste Data