asked on

C++ -- Adding a Constraint

I'm working on a developing a program that meets the "0-1 Knapsack" concept. See URL below for more conceptual details:
http://en.wikipedia.org/wiki/Knapsack_problem

Right now, I've developed the basic framework (I googled for existing code and tried to modify it).

At this point, the code below somewhat works. By "somewhat", I mean that it doesn't meet the "0-1 Knapsack" concept. Essentially, the program adds four items of #3 (based on its greatest value contribution)... and then adds #1 due to the remaining (unfilled) weight capacity.

So, while the code does determine the greatest value contribution, I want to modify it so that I only can add one item at the most to the knapsack.

Does anyone know how to add this constraint (i.e, once an added has been selected for the knapsack, remove it from the array so that I can't be selected again)?

Thx,
EEH

P.S. Also, as this is not my original code, I'm having a tough time understanding the ForLoop and WhileLoop. If anyone could "walk me through" this (by adding a few comments), it would greatly help me in the continuation of the program development. Again, thanks!!!

P.S.S. If you think that this code is too cumbersome and could work better using a different method, I"m open to recommendations.

// Required C++ libraries and header files
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdlib>
#include <math.h>                                                                                    
#include <limits.h>
using namespace std;

int linecount = 10;															    // The number of objects 
#define MAXWEIGHT 900
int knapSack_Max_Weight = 900;

int knapSack_Max_Volume = 800;
														
int itemValue[10]  = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575};			// Item's itemValue
int itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300};		// Item's itemVolume
int itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400};		// Item's itemWeight

// Declarations of independent functions
void knapsackGreedy();


int main()
{		
	// Function call
	knapsackGreedy();

	// Pause the window console screen
    system("PAUSE");
    return 0;
}


void knapsackGreedy() {
	int a[MAXWEIGHT];						// a[i] holds the maximum itemValue that can be obtained using at most i itemWeight 
	int lastAddedItem[MAXWEIGHT];			// Calculate which objects were added
	int i, j;
	int aux;

	for (i=0; i<=knapSack_Max_Weight; ++i) {
		a[i] = 0;
		lastAddedItem[i] = -1;
	}

	a[0] = 0;
	for (i=1; i<=knapSack_Max_Weight; ++i)
		for (j=0; j<linecount; ++j)
			if ((itemWeight[j] <= i) && (a[i] < a[i - itemWeight[j]] + itemValue[j])) {
				a[i] = a[i - itemWeight[j]] + itemValue[j];
				lastAddedItem[i] = j;
			}

	aux = knapSack_Max_Weight;
	while ((aux > 0) && (lastAddedItem[aux] != -1)) {
		std::cout << "Added item# " << lastAddedItem[aux] + 1 << " (" << itemValue[lastAddedItem[aux]] << " value units; " << itemWeight[lastAddedItem[aux]] <<" weight units). " << " Weight capacity left: " << aux - itemWeight[lastAddedItem[aux]] << std::endl;
        aux -= itemWeight[lastAddedItem[aux]];
	}

	cout << endl << endl;
	cout << "The selected items equal " << a[knapSack_Max_Weight] << " value units." << endl << endl << endl;
}

Open in new window

Christian de Bellefeuille

According to Wikipedia article, Greedy approximation algorithm is not the best method for 0-1. You could probably add some conditions to add 1 item of each maximum, but it wouldn't be optimal.

I've already coded C++ years ago, but actually the language is not the problem. I'll read a bit about the knapsack to find a way to compute that.