Double Knapsack Problem
user_3763047219
c_cpp
3 years ago
1.1 kB
5
Indexable
#include <iostream> int main() { int n = 0, W = 0, V = 0; int c[101] = {}, w[101] = {}, v[101] = {}; scanf("%d%d%d", &n, &W, &V); for (int i = 1; i <= n; i++) { scanf("%d", &c[i]); } for (int i = 1; i <= n; i++) { scanf("%d", &w[i]); } for (int i = 1; i <= n; i++) { scanf("%d", &v[i]); } static int T[101][1001][1001] = {0}; for (int i = 1; i <= n; i++) { for (int j = 1; j <= W; j++) { for (int k = 1; k <= V; k++) { if (w[i] > j || v[i] > k) { T[i][j][k] = T[i - 1][j][k]; } else { if (T[i - 1][j][k] < T[i - 1][j - w[i]][k - v[i]] + c[i]) { T[i][j][k] = T[i - 1][j - w[i]][k - v[i]] + c[i]; } else { T[i][j][k] = T[i - 1][j][k]; } } } } } int pw = W, pv = V; int value = 0; int total = 0; int ans[101] = {}; for (int i = n; i >= 1; i--) { if (T[i][pw][pv] != T[i - 1][pw][pv]) { value = value + c[i]; total++; ans[total] = i; pw = pw - w[i]; pv = pv - v[i]; } } printf("%d\n%d\n", value, total); for (int i = total; i >= 1; i--) { printf("%d ", ans[i]); } }
Editor is loading...