Knapsack problem with cpp

knapsack.cpp

#include <iostream>
#include <bitset>
#include <algorithm>
#include <string>

#include <math.h>
#include <string.h>
#include <pthread.h>

#define N 8
#define MAX (N - 1)
#define MAXBIT (pow(2, N) - 1)

#define PROC 4

const int max_size = 25;

const int content_size[N] = {3, 6, 5, 4, 8, 5, 3, 4};
const int prices[N] = {7, 12, 9, 7, 13, 8, 4, 5};

using namespace std;

typedef struct
{
	int high;
	int low;
	int most_price;
	int most_size;
	bitset<N> max_bit;
} Range;

Range ranges[PROC];

inline
void *bluteforce(void *arg)
{
	int *r = (int *)arg;
	int i, j, sum_size, sum_price, most_price, most_size;

	bitset<N> bit;
	bitset<N> max;
	// Compare at a part of threads
	for (i = ranges[*r].low; i < ranges[*r].high; bit = bitset<N>(++i))
	{
		sum_price = sum_size = 0;
		for (j = 0; j < N; j++)
			if (bit[j]) // Is flagged
			{
				sum_size += content_size[j];
				sum_price += prices[j]; 
			}

		if (sum_size <= max_size && most_price <= sum_price)
		{
			most_price = sum_price;
			most_size = sum_size;
			max = bit;
		}
	}
	ranges[*r].most_price = most_price;
	ranges[*r].most_size = most_size;
	ranges[*r].max_bit = max; 
	pthread_exit(NULL);
}

inline
void reverse(char *(&s))
{
	char c;
	int n = N / 2;
	for (int i = 0; i < n; i++)
	{
		c = s[i];
		s[i] = s[MAX - i];
		s[MAX - i] = c;
	}
}

int main(int argc, char *argv[])
{	
	int i;
	int most_price, most_size;

	// Assignment size
	int r = MAXBIT / PROC;
	for (i = 0; i < PROC - 1; i++)
	{
		ranges[i].low = r * i;
		ranges[i].high = ranges[i].low + r;
	}

	// Only last
	ranges[i].low = r * i;
	ranges[i].high = MAXBIT - ranges[i].low;

	// Create thread
	pthread_t *pt = (pthread_t*)malloc(PROC * sizeof(pthread_t));
	for (i = PROC - 1; i >= 0; i--)
		pthread_create(&pt[i], NULL, bluteforce, (void *)&i);

	// Wait for all threads
	usleep(1);
	for (i = PROC - 1; i >= 0; i--)
		pthread_join(pt[i], NULL);

	// Final compare
	bitset<N> max;

	for (i = 0; i < PROC; i++)
		if (most_price <= ranges[i].most_price)
		{
			most_price = ranges[i].most_price;
			most_size = ranges[i].most_size;
			max = ranges[i].max_bit;
		}

	char *s = strdup(max.to_string().c_str());
	reverse(s);

	cout << "size: " << most_size << endl;
	cout << "price: " << most_price << endl;
	cout << s << endl;
    return 0;
}

size: 25
price: 45
11101010