1051背包

#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 = 0; i < n; i++) {
		scanf("%d", &v[i]);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &w[i]);
	}
	scanf("%d", &W);

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

}