Constrained 0-1 Knapsack Problem

Constrained 0-1 Knapsack Problem.cpp

#include <bits/stdc++.h>

using namespace std;

struct Data {
	int v, w;
};

bool solve()
{
	int n, l, wa, wb;
	scanf("%d %d %d %d", &n, &l, &wa, &wb);

	Data inp[n];
	for (int i = 0; i < n; i++)
		scanf("%d %d", &inp[i].v, &inp[i].w);

	int ans = -1;
	for (int i = 0; i < (1 << n); i++) {
		int totalWeight = 0;
		int totalValue = 0;
		if (__builtin_popcount(i) >= l) {
			for (int j = 0; j < n; j++) {
				if ((i >> j) & 1) {
					totalWeight += inp[j].w;
					totalValue += inp[j].v;
				}
			}

			if (wa <= totalWeight && totalWeight <= wb)
				ans = max(ans, (totalValue + totalWeight - 1) / totalWeight);
		}
	}

	printf("%d\n", ans);

	int end;
	scanf("%d", &end);

	return end == 0;
}

int main()
{
	while (1)
		if (solve() == false)
			break;
	return 0;
}