StoneHaos

8

Nov 21st, 2021 (edited)
349
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <limits.h>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. const int w = 14;
  9. const int n = 10;
  10.  
  11. const int u[n + 1] = {0, 11, 94, 61, 52, 47, 78, 73, 90, 91, 97};
  12. const int v[n + 1] = {0, 6, 9, 4, 6, 10, 10, 4, 2, 3, 3};
  13.  
  14. int dp[n + 1][w + 1];
  15.  
  16. int main(void) {
  17.     for (int i = 0; i <= n; ++ i)
  18.         dp[i][0] = 0;
  19.     for (int i = 0; i <= w; ++ i)
  20.         dp[0][i] = 0;
  21.  
  22.     for (int i = 1; i <= n; ++ i) {
  23.         for (int j = 1; j <= w; ++ j) {
  24.             dp[i][j] = dp[i - 1][j];
  25.             if (v[i] <= j)
  26.                 dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + u[i]);
  27.         }
  28.     }
  29.  
  30.     for (int i = 0; i <= n; ++ i) {
  31.         for (int j = 0; j <= w; ++ j)
  32.             cout << dp[i][j] << " ";
  33.         cout << endl;
  34.     }
  35.     vector<int> p;
  36.     int i = n;
  37.     int j = w;
  38.     int x = dp[i][j];
  39.     while (i != 0 && j != 0) {
  40.         i --;
  41.         if (x != dp[i][j]) {
  42.             j -= v[i + 1];
  43.             x = dp[i][j];
  44.             p.push_back(i + 1);
  45.         }
  46.     }
  47.  
  48.  
  49.     reverse(p.begin(), p.end());
  50.     int a = 0;
  51.     int b = 0;
  52.     cout << endl;
  53.     for (int i = 0; i < p.size(); ++ i) {
  54.         cout << p[i] << " ";
  55.         a += u[p[i]];
  56.         b += v[p[i]];
  57.     }
  58.     cout << endl << a << " " << b << endl;
  59.     return 0;
  60. }
RAW Paste Data Copied