01Knapsack Problem 背包

#include <iostream>

int main()
{
	int n = 0, W = 0, q = 0;
	int v[101] = {}, w[101] = {};
	static int T[101][101] = {};
	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 = 1; i <= n; i++) {
		int q2 = 0;
		for (int j = 1; j <= W; j++) {
			if (w[i] > j) {
				T[i][j] = T[i - 1][j];
			}
			else {
				if (T[i - 1][j] < T[i - 1][j - w[i]] + v[i]) {//維持原樣的 < 多放一個物品的價值
					T[i][j] = T[i - 1][j - w[i]] + v[i];
				}
				else {
					T[i][j] = T[i - 1][j];
				}
			}
		}
	}
	int pw = W;
	int T2 = 0;
	int s[101] = {0};//紀錄是否要放第i個物品
	int ans[101] = { 0 };
	int index = 1;
	for (int i = n; i >= 1; i--) {//從最後找回去
		if (T[i][pw] == T[i - 1][pw]) {
			s[i] = 0;
		}
		else {
			s[i] = 1;
			pw = pw - w[i];
			T2 = T2 + v[i];
			q = q + 1;
			ans[index] = i;
			index++;
		}

	}
	printf("%d\n", T2);
	printf("%d\n", q);
	printf("(%d", ans[index-1]);

	for (int i = index-2 ; i >= 1; i--) {
		printf(",%d", ans[i]);
	}
	printf(")");
}