~~~ void dp(int *w, int *v, int n, int c){ int **m; m = new int*[n+1]; for (int i = 0; i<n + 1; i++) { m[i] = new int[c+1]; for (int j = 0; j<c + 1; j++) m[i][j]=0; } for (int i = w[n - 1]; i <= c; i++) m[n][i] = v[n - 1]; for (int i = n - 1; i >= 2; i--){ for (int j = c; j >= 1; j--){ if (j - w[i - 1] >= 0){ int tmp = m[i + 1][j - w[i - 1]] + v[i - 1]; m[i][j] = m[i + 1][j]>tmp ? m[i + 1][j] : tmp; } else{ m[i][j] = m[i + 1][j]; } } } if (c >= w[0]) m[1][c] = m[2][c - w[0]] + v[0]; else m[1][c] = m[2][c]; // for (int i = 1; i <= n; i++) { // for (int j = 1; j <= c; j++) cout << m[i][j] << "\t"; // cout << endl; // } int *x; x = new int[n+1]; for (int i = 0; i<n + 1; i++) x[i]=0; if (m[1][c] == m[2][c]) x[1] = 0; else x[1] = 1; int j = c; for (int i = 2; i <n; i++){ if (x[i - 1] == 0){ if (m[i][j] == m[i + 1][j]) x[i] = 0; else { x[i] = 1; } } else{ j = j - w[i - 2]; if (m[i][j] == m[i + 1][j]) x[i] = 0; else { x[i] = 1; } } } if (m[n][c] == 0) x[n] = 0; else x[n] = 1; // for (int i = 1; i <= n; i++) cout << x[i] << "\t"; cout << endl; } ~~~