/**
 * Compile: gcc-mp-4.3 knapsack_bfs.cpp -fopenmp -lstdc++
 */

#include <omp.h>
#include <vector>
#include <deque>
#include <stdio.h>

int $capacity;

struct Object {
	int weight;
	int price;
};
std::vector<Object> $objects;

struct Node {
	int iobject;
	int sum_weights;
	int sum_prices;
};
std::deque<Node> $queue;

void load_data(const char *file_name);
int knap_bfs();
int process_node(Node node);

int main() {
	int opt;
	
	load_data("knapsack.dat");
	opt = knap_bfs();
	printf("opt = %d\n", opt);
	
	return 0; 
} 

void load_data(const char *file_name) {
	FILE             *file;
	int              num_objects;
	std::vector<int> weights;
	std::vector<int> prices;
	Object           object;
	int              i, tmp;

	file = fopen(file_name, "r");
	
	fscanf(file, "%d", &num_objects);
	fscanf(file, "%d", &$capacity);
	for (i = 0; i < num_objects; i++) {
		fscanf(file, "%d", &tmp);
		weights.push_back(tmp);
	}
	for (i = 0; i < num_objects; i++) {
		fscanf(file, "%d", &tmp);
		prices.push_back(tmp);
	}

	for (i = 0; i < num_objects; i++) {
		object.weight = weights.at(i);
		object.price  = prices.at(i);
		$objects.push_back(object);
	}

	fclose(file); 
}

/**
 * Perform the BFS algorithm.
 */
int knap_bfs() {
	int  ret;
	int  tmp;
	Node node;

	ret = 0;
	node.iobject     = 0;
	node.sum_weights = 0;
	node.sum_prices  = 0;
	$queue.push_back(node);
	while (!$queue.empty()) {
		node = $queue.front();
		$queue.pop_front();

		tmp = process_node(node);
		if (ret < tmp) {
			ret = tmp;
		}
	}
	
	return ret;
}

/**
 * Returns the optimal price at this node.
 */
int process_node(Node node) {
	int    ret;
	Object object;
	Node   new_node;
	
	ret = node.sum_prices;
	object = $objects.at(node.iobject);

#pragma omp parallel sections num_threads(2) shared($queue) 
{
	#pragma omp section
	{
	// Do not take this object
	if (node.iobject < $objects.size() - 1) {
		new_node.iobject     = node.iobject + 1;
		new_node.sum_weights = node.sum_weights;
		new_node.sum_prices  = node.sum_prices;
		$queue.push_back(new_node);
	}
	}
	
	#pragma omp section
	{
	// Take this object
	if (node.sum_weights + object.weight <= $capacity) {
		if (node.iobject < $objects.size() - 1) {
			new_node.iobject     = node.iobject + 1;
			new_node.sum_weights = node.sum_weights + object.weight;
			new_node.sum_prices  = node.sum_prices  + object.price;
			$queue.push_back(new_node);
		
			ret = new_node.sum_prices;
		} 
	}
	}
}

	return ret;
}