Source

IntroToAlgorithm3ed / src / NCKUAlg / ProgHW4 / knapsack01 / knapsack01.c

Full commit
/*
 * Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+HW4@gmail.com)
 * This file is a part of introtoalgorithm3ed.
 *
 * introtoalgorithm3ed is a free software; you can redistribute it and/or modify it under the terms of the GNU General
 * Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option)
 * any later version.
 *
 * This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
 * License for more details.
 *
 * You should have received a copy of the GNU General Public License along with this source file; if not, write to the
 * Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Items {
	int *WeightsPtr;
	int *ValuesPtr;
	int *HowManyPtr;
	int TotalItemNum;
	int arrLength;
	int arrLimit;
};
int max(int a, int b);
int main(int argc, char *argv[]) {
	char *inputFileName, *outputFileName;
	if (argc == 1) {
		inputFileName = "./test2.txt";
		outputFileName = "./output.txt";
	} else {
		inputFileName = argv[1];
		outputFileName = argv[2];
	}
	FILE *inputFile = fopen(inputFileName, "r");
	FILE *outputFile = fopen(outputFileName, "w");
	if (inputFile == NULL || outputFile == NULL) {
		printf("Program terminates because %s can't be found\n", inputFileName);
		exit(1);
	}
	const int maxDigits = 128;
	char aLine[maxDigits], *numberStr;
	fgets(aLine, sizeof aLine, inputFile); //get rid of the first line
	fgets(aLine, sizeof aLine, inputFile); //read knapsack limit
	int *tempPtr = realloc(NULL, sizeof(int) * 20);
	struct Items items = { realloc(NULL, sizeof(int) * 20), realloc(NULL,
			sizeof(int) * 20), realloc(NULL, sizeof(int) * 20), 0, 0, 20 };
	int knapsackLimit = atoi(aLine), index = 0;
	printf("Reading input file...\n");
	fprintf(outputFile, "Reading input file...\n");
	while (fgets(aLine, sizeof aLine, inputFile) != NULL) //read a line
	{
		numberStr = strtok(aLine, " \n");
		items.WeightsPtr[index] = atoi(numberStr);
		numberStr = strtok(NULL, " \n");
		items.ValuesPtr[index] = atoi(numberStr);
		numberStr = strtok(NULL, " \n");
		items.HowManyPtr[index] = atoi(numberStr);
		(items.TotalItemNum) += items.HowManyPtr[index];
		printf("items: weights=%d, values:%d, howMany:%d\n",
				items.WeightsPtr[index], items.ValuesPtr[index],
				items.HowManyPtr[index]);
		fprintf(outputFile, "items: weights=%d, values:%d, howMany:%d\n",
				items.WeightsPtr[index], items.ValuesPtr[index],
				items.HowManyPtr[index]);
		index++;
		if (index > items.arrLimit - 1) {
			(items.arrLimit) *= 2;
			tempPtr = realloc(items.WeightsPtr, items.arrLimit * sizeof(int));
			int i;
			for (i = 0; i < index; i++)
				tempPtr[i] = items.WeightsPtr[i];
			items.WeightsPtr = realloc(items.WeightsPtr,
					items.arrLimit * sizeof(int));
			for (i = 0; i < index; i++)
				items.WeightsPtr[i] = tempPtr[i];
			for (i = 0; i < index; i++)
				tempPtr[i] = items.ValuesPtr[i];
			items.ValuesPtr = realloc(items.ValuesPtr,
					items.arrLimit * sizeof(int));
			for (i = 0; i < index; i++)
				items.ValuesPtr[i] = tempPtr[i];
			for (i = 0; i < index; i++)
				tempPtr[i] = items.HowManyPtr[i];
			items.HowManyPtr = realloc(items.HowManyPtr,
					items.arrLimit * sizeof(int));
			for (i = 0; i < index; i++)
				items.HowManyPtr[i] = tempPtr[i];
		}
	}
	fclose(inputFile);
	int bestValues[items.TotalItemNum + 1][knapsackLimit + 1],
			addItem[items.TotalItemNum + 1][knapsackLimit + 1];
	int howManyItemUsed = 0, itemType = 0, totalItemNum, knapsackSize;
	//!!!!It's crucial to initialize these 2 arrays correctly from "knapsackSize=0" and "totalItemNum=0"
	for (knapsackSize = 0; knapsackSize <= knapsackLimit; knapsackSize++) { //init first row when there's no item to grab
		bestValues[0][knapsackSize] = 0;
		addItem[0][knapsackSize] = 0;
	}
	for (totalItemNum = 0; totalItemNum <= items.TotalItemNum; totalItemNum++) { //init first col when knapsackSize==0
		bestValues[totalItemNum][0] = 0;
		addItem[totalItemNum][0] = 0;
	}
	printf("Solving problem using dynamic programming...\n");
	fprintf(outputFile, "Solving problem using dynamic programming...\n");
	for (totalItemNum = 1; totalItemNum <= items.TotalItemNum; totalItemNum++) {
		if (totalItemNum > items.HowManyPtr[itemType] + howManyItemUsed) { //run out of items of itemType, so start using another type of items
			howManyItemUsed = totalItemNum - 1;
			itemType++;
		}
		for (knapsackSize = 1; knapsackSize <= knapsackLimit; knapsackSize++) {
			if (items.WeightsPtr[itemType] <= knapsackSize) {
				bestValues[totalItemNum][knapsackSize] = max(
						bestValues[totalItemNum - 1][knapsackSize],
						items.ValuesPtr[itemType]
								+ bestValues[totalItemNum - 1][knapsackSize
										- items.WeightsPtr[itemType]]);
				/*if bestValues[totalItemNum][knapsackSize]==items.ValuesPtr[itemType]+bestValues[totalItemNum-1][knapsackSize-items.WeightsPtr[itemType]]: this indicates that we'll'get a higher value by replacing
				 previous item with a "new" item(i.e. items.ValuesPtr[itemType])+ max value that can be attained using the remaining space(i.e. bestValues[totalItemNum-1][knapsackSize-items.Weights[itemType]])
				 if bestValues[totalItemNum][knapsackSize]==bestValues[totalItemNum-1][knapsackSize]: we'll get a better value by not replacing the previous item with the new item*/
				addItem[totalItemNum][knapsackSize] =
						(bestValues[totalItemNum - 1][knapsackSize]
								> items.ValuesPtr[itemType]
										+ bestValues[totalItemNum - 1][knapsackSize
												- items.WeightsPtr[itemType]]) ?
								0 : 1; //0: do not add new element, 1: add
			} else { //there's not enough room for adding another item of itemType so keep the previous best
				bestValues[totalItemNum][knapsackSize] = bestValues[totalItemNum
						- 1][knapsackSize];
				addItem[totalItemNum][knapsackSize] = 0;
			}
		}
	}
	printf("Traverse addItem matrix to obtain the optimal solution...\n");
	fprintf(outputFile,
			"Traverse addItem matrix to obtain the optimal solution...\n");
	//traverse addItem matrix to determine which items should we take
	int *whichItemToAddPtr = realloc(NULL, sizeof(int) * 20),
			whichItemToAddSize = 0, whichItemToAddSizeLimit = 20, weightLeft =
					knapsackLimit;
	itemType = (index - 1);
	howManyItemUsed = 0;
//	whichItemToAdd, weightLeft, itemType, howManyItemUsed := make([]int, 0), knapsackLimit, len(items.Weights)-1, 0
	for (totalItemNum = items.TotalItemNum; totalItemNum > 0; totalItemNum--) {
		// fmt.Println("totalItemNum",totalItemNum)
		// fmt.Println("items.TotalItemNum",items.TotalItemNum)
		// fmt.Println("itemType",itemType)
		if (totalItemNum
				<= items.TotalItemNum - howManyItemUsed
						- items.HowManyPtr[itemType]) {
			howManyItemUsed += items.HowManyPtr[itemType];
			itemType--;
		}
		// fmt.Println(itemType)
		// fmt.Println(weightLeft)
		if (weightLeft > 0 && addItem[totalItemNum][weightLeft] == 1) {
			whichItemToAddPtr[whichItemToAddSize] = itemType + 1;
			if (whichItemToAddSize + 1 > whichItemToAddSizeLimit) {
				whichItemToAddSizeLimit *= 2;
				whichItemToAddPtr = realloc(whichItemToAddPtr,
						whichItemToAddSizeLimit * sizeof(int));
			}
			weightLeft -= items.WeightsPtr[itemType];
			whichItemToAddSize++;
		}
	}
	printf("\nResults:\n");
	fprintf(outputFile, "\nResults:\n");
	printf("Optimal value:%d\n", bestValues[items.TotalItemNum][knapsackLimit]);
	fprintf(outputFile, "Optimal value:%d\n",
			bestValues[items.TotalItemNum][knapsackLimit]);
	printf("We need to take items: [");
	fprintf(outputFile, "We need to take items: [");
	int count;
	for (count = 0; count < whichItemToAddSize; count++) {
		printf(" %d", whichItemToAddPtr[count]);
		fprintf(outputFile, " %d", whichItemToAddPtr[count]);
	}
	printf(" ]\n\n");
	fprintf(outputFile, " ]\n\n");
	fclose(outputFile);
	return 0;
}
int max(int a, int b) {
	if (a > b) {
		return a; //0 do not add new element
	} else {
		return b; //1 add
	}
	return -1;
}