#define MAX_N 100 

int N;         // Number of objects
int CAP;       // Capacity
int W[MAX_N];  // Weights
int P[MAX_N];  // Prices

#include <stdio.h>

int main() {
	int opt;

	read_data_file("knapsack.dat"); 
	opt = knap_search(0, 0, CAP); 
	printf("opt = %d\n", opt);
	
	return 0; 
} 

read_data_file(char *file) {
	FILE *fp; 
	int i; 
	
	fp = fopen(file, "r"); 
	fscanf(fp, "%d", &N); 
	fscanf(fp, "%d", &CAP); 
	for (i= 0; i < N; i++) { 
		fscanf(fp, "%d", &W[i]); 
	}
	for (i= 0; i < N; i++) {
		fscanf(fp, "%d", &P[i]);
	}
	fclose(fp); 
} 

/**
 * DFS
 * i:  Index in W or P
 * cp: Current sum of prices
 * m:  Capacity left
 */
int knap_search(int i, int cp, int m) {
	int opt; 
	int l, r; 

	if (i < N && m > 0) { 
		if (m >= W[i]) {
#pragma omp parallel sections num_threads(2)
{
	#pragma omp section
	{
			l = knap_search(i + 1, cp + P[i], m - W[i]);
	}
	#pragma omp section
	{
			r = knap_search(i + 1, cp, m);
	}
}
			if (l > r) {
				opt = l; 
			} else {
				opt = r; 
			}
		} else {
			opt = knap_search(i + 1, cp, m); 
		}
	} else {
		opt = cp;
	}

	return opt; 
}