Double Knapsack Problem

 avatar
user_3763047219
c_cpp
2 years ago
1.1 kB
1
Indexable
Never
#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]);
	}
}