遞迴_背包

#include <stdio.h>

int max(int a, int b) {
	if (a > b) {
		return a;
	}
	else {
		return b;
	}
}
int pack(int w, int W[], int V[],int index,int value) {
	while (index >= 0) {
		if (index == 0) {
			return value;
		}
		else if (W[index] > w) {
			return pack(w, W, V, index-1, value);
		}
		else if (W[index] <= w) {
			return max(pack(w - W[index], W, V, index-1, value + V[index]), pack(w, W, V, index-1, value));
		}
	}
}

int main() {
	int n = 0, w = 0;
	scanf("%d %d", &n, &w);
	int W[21] = {}, V[21] = {};
	for (int i = 1; i <= n; i++) {
		scanf("%d %d", &W[i], &V[i]);
	}
	printf("%d", pack(w, W, V, n,0));
}