Advertisement
StoneHaos

8

Jan 23rd, 2022
907
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.93 KB | None | 0 0
  1. #include <stdio.h>
  2. using namespace std;
  3. int main() {
  4.     const int k = 10, W = 14;
  5.     const int w[] = {0, 3, 7, 6, 2, 7, 7, 2, 3, 6, 5};
  6.     const int p[] = {0, 61, 91, 41, 18, 92, 67, 12, 36, 30, 52};
  7.  
  8.     int A[k + 1][W + 1];
  9.     for (int i = 0; i <= k; i++) A[i][0] = 0;
  10.     for (int n = 0; n <= W; n++) A[0][n] = 0;
  11.     for (int s = 1; s <= k; s++) {
  12.         for(int n = 1;n<=W;n++) {
  13.             A[s][n] = A[s-1][n];
  14.             if (n >= w[s] && (A[s - 1][n - w[s]] + p[s] > A[s][n])) A[s][n] = A[s - 1][n - w[s]] + p[s];
  15.         }
  16.  
  17.     }      
  18.     for (int i = 0; i <= k; i++) {
  19.         for (int j = 0; j <= W; j++)
  20.             printf("%d ", A[i][j]);
  21.         printf("\n");
  22.     }
  23.     printf("\n%d\n", A[k][W]);
  24.     int arr[k];
  25.     int brd = 0;
  26.     int a = k, b = W, t = A[a][b];
  27.     while (a && b) {
  28.         a --;
  29.         if (t != A[a][b]) {
  30.             b -= w[a + 1];
  31.             t = A[a][b];
  32.             arr[brd++] = a + 1;
  33.         }
  34.     }
  35.  
  36.     for (int i = brd - 1; i >= 0; i --) {
  37.         printf("%d ", arr[i]);
  38.     }
  39.     printf("\n");
  40.     return 0;
  41.  
  42.  
  43.  
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement