#include "kp.h"

static void solveKnapsack(knapsackT knapsack);

void knapsackMain(char *filename){
	knapsackT nKnapsack;

	nKnapsack = readkpMatrixFromFile(filename);
	printKP(nKnapsack);

	solveKnapsack(nKnapsack);

}

static void solveKnapsack(knapsackT knapsack){
	int i, j, k, **matrix, **keepTable, currentNumberofItems, itemsinkp, weigth,row, weightLeft;



	row=0;
	matrix = KPmatrix(knapsack.capacity, knapsack.size);
	keepTable = KPmatrix(knapsack.capacity, knapsack.size);

	if(knapsack.capacity == 0){
		Error("You cant pack anything in a small bag you dumbass\n");
	}
	//creating the value and 1/0 keeper tablet
	while(row <= knapsack.capacity){
		if(row==0){
			for(i=1;i<=knapsack.capacity;i++){
				matrix[i][row] = 0;
				keepTable[i][row] = 0;
			}
		}
		else{
			//får item platts i knapsack?
			for(i=1; i < knapsack.capacity; i++){
				if(knapsack.item[row].weight > i){
					//om itemet inte får platts kopieras värder åvanför
					matrix[i][row] = matrix[i][row-1];
					keepTable[i][row] = 0;
				}
				else{
					weightLeft = knapsack.item[row].weight -i;

					if(database->matris[1][row]+values[weightLeft][row-1] > values[i][row-1]){
						values[i][row] = database->matris[1][row]+values[weightLeft][row-1];
						keeper[i][row] = 1;
					}
					else{
						values[i][row] =  values[i][row-1];
						keeper[i][row] = 0;
					}
				}
			}
		}
		row = row+1;
	}

	//we now got our keeper tablet,lets use it!
	printf("For a optimal solotion use:\n");
	weightLeft = database->knapsackCap;
	totalPoints = 0;
	for(i=database->nrOfitems; i < 0; i--){
		if(keeper[weightLeft][i] == 1){
			//then pick item.
			printf("Item nr: %d\n", database->matris[0][i-1]);
			printf("Item with value %d\n", database->matris[1][i-1]);
			totalPoints = totalPoints + database->matris[1][i-1];
			weightLeft = weightLeft - database->matris[2][i-1];
			printf("\n");
		}
	}
	printf("The optimal value is: %d\n", totalPoints);
}


}


/*
typedef struct{
	int nrOfitems;
	int **matris;
	int knapsackCap;
}*dbT;

/*Functions*//*
dbT readKpFile(void);
int** NewKpValueMatris(int size);
void printKpMatris(int **matris, int size);
int getValueOf(int itemI, int **matris);
int getWeightOf(int itemI, int **matris);
int** NewKpVolumeAndKeepMatris(int cap, int nrOfitems);
void KpSolv(dbT database);
main(){
	dbT database;
	int i, **values, **keeper;
	database = readKpFile();
	KpSolv(database);
}

int getValueOf(int itemI, int **matris){
	return matris[1][itemI-1];
}
int getWeightOf(int itemI, int **matris){
	return matris[2][itemI-1];
}
dbT readKpFile(void){

	FILE *fp;
	int size, **matris, kapsackCap, nr, value, weight, i;
	dbT db;
	char *filename;

	db = New(dbT);
	filename = GetLine();
	fp = fopen(filename, "r");
	if(fp == NULL){Error("Error reading file\n");}
	fscanf(fp, "%d", &size);
	db->nrOfitems = size;
	matris = NewKpValueMatris(size);


	for(i=0;i<size;i++){
		if(fp == NULL){Error("Error reading file\n");}
		fscanf(fp, "%5d %5d %5d",&matris[0][i], &matris[1][i],&matris[2][i]);

		//printf("%5d %5d %5d\n",matris[0][i], matris[1][i],matris[2][i]);
	}
	db->matris = matris;
	fscanf(fp, "%d", &kapsackCap);
	db->knapsackCap = kapsackCap;
	fclose(fp);
	return db;
}
int** NewKpValueMatris(int size){
	int i, **matris;
	matris = (int**)calloc(3, sizeof(int));		//Allokerar matrisen, 3 i vågrät, nr-value-weight
	for(i = 0 ; i < size ; i++){
		matris[i] = (int*)calloc(size, sizeof(int));
	}
	return matris;
}
void printKpMatris(int **matris, int size){
	int i;

	for(i = 0 ; i < size; i++){
		printf("%5d %5d %5d\n",matris[0][i], matris[1][i],matris[2][i]);
	}
		printf("\n");
}
int** NewKpVolumeAndKeepMatris(int cap, int nrOfitems){
	int i, **matris;
	matris = (int**)calloc(cap, sizeof(int));		//Allokerar matrisen, cap i vågrätt och nrofitems i lodräd + 1(pga första raden är 0
	for(i = 0 ; i < (nrOfitems+1) ; i++){
		matris[i] = (int*)calloc((nrOfitems+1), sizeof(int));
	}
	return matris;
}

void KpSolv(dbT database){
	int i, weightLeft, **values, **keeper, row, totalPoints;

	row=0;
	values = NewKpVolumeAndKeepMatris(database->knapsackCap, database->nrOfitems);
	keeper = NewKpVolumeAndKeepMatris(database->knapsackCap, database->nrOfitems);

	if(database->knapsackCap == 0){
		Error("You cant pack anything in a empty bag you dumbass\n");
	}
	//creating the value and 1/0 keeper tablet
	while(row <= database->knapsackCap){
		if(row==0){
			for(i=1;i<=database->knapsackCap;i++){
				values[i][row] = 0;
				keeper[i][row] = 0;
			}
		}
		else{
			//får item platts i knapsack?
			for(i=1; i < database->knapsackCap; i++){
				if(database->matris[2][row] > i){
					values[i][row] = values[i][row-1];
					keeper[i][row] = 0;
				}
				else{
					weightLeft = database->matris[2][row]-i;

					if(database->matris[1][row]+values[weightLeft][row-1] > values[i][row-1]){
						values[i][row] = database->matris[1][row]+values[weightLeft][row-1];
						keeper[i][row] = 1;
					}
					else{
						values[i][row] =  values[i][row-1];
						keeper[i][row] = 0;
					}
				}
			}
		}
		row = row+1;
	}

	//we now got our keeper tablet,lets use it!
	printf("For a optimal solotion use:\n");
	weightLeft = database->knapsackCap;
	totalPoints = 0;
	for(i=database->nrOfitems; i < 0; i--){
		if(keeper[weightLeft][i] == 1){
			//then pick item.
			printf("Item nr: %d\n", database->matris[0][i-1]);
			printf("Item with value %d\n", database->matris[1][i-1]);
			totalPoints = totalPoints + database->matris[1][i-1];
			weightLeft = weightLeft - database->matris[2][i-1];
			printf("\n");
		}
	}
	printf("The optimal value is: %d\n", totalPoints);
}
*/