#include<iostream>
using namespace std;
#define max 100
int bag(int current_weight, int n, int weights[], int values[]) {
	if (n == 0 || current_weight == 0) {

		return 0;
	}
	if (weights[n - 1] > current_weight) {

		return bag(current_weight, n - 1, weights, values);
	}
	if (weights[n - 1] <= current_weight) {
		
		return bag(current_weight - weights[n - 1], n - 1, weights, values) + values[n - 1] > bag(current_weight, n - 1, weights, values) ? bag(current_weight - weights[n - 1], n - 1, weights, values) + values[n - 1] : bag(current_weight, n - 1, weights, values);

	}
}
int main() {
	int numbers;
	int values[max];
	int weights[max];
	int weight;
	cout << "请输入物品数量:";
	cin >> numbers;
	cout << endl;
	cout << "请输入背包能容纳的重量:";
	cin >> weight;
	system("cls");
	for (int i = 0; i < numbers; i++) {
		cout << "请输入第" << i + 1 << "个物品的价值:";
		cin >> values[i];
		cout << endl;
		cout << "请输入第" << i + 1 << "个物品的重量:";
		cin >> weights[i];
		system("cls");
	}
	cout << "您可获得的最大价值为" << bag(weight, numbers, weights, values);
}