105e Knapsack Problem

 avatar
user_3763047219
c_cpp
2 years ago
1.1 kB
2
Indexable
Never
#include <iostream>

int main()
{
	int n = 0;
	int v[101] = {}, w[101] = {};
	int W = 0;
	static int c[101][1001] = {};
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &v[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
	}
	scanf("%d", &W);

	for (int i = 0; i <= n; i++) {
		for (int j = 1; j <= W - w[1]; j++) {
			c[i][j] = v[1];
		}
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 1; j <= W - w[1]; j++) {
			if (w[i] > j) {
				c[i][j] = c[i - 1][j];
			}
			else {
				if (c[i - 1][j] < c[i - 1][j - w[i]] + v[i]) {
					c[i][j] = c[i - 1][j - w[i]] + v[i];
				}
				else {
					c[i][j] = c[i - 1][j];
				}
			}
		}
	}

	int pw = W - w[1];
	int ans[101] = {};
	int value = v[1];
	int total = 0;
	for (int i = n; i >= 2; i--) {
		if (c[i][pw] != c[i - 1][pw]) {
			total = total + 1;
			ans[total] = i ;
			value = value + v[i];
			pw = pw - w[i];
		}
	}
	printf("%d\n%d\n", value , total+1);
	printf("(1");
	for (int i = total; i >= 1; i--) {
		printf(",%d", ans[i]);
	}
	printf(")");

}