SPOJ: PARTY (spoiler alert)

[Script Coder]

I have coded a solution to the problem: http://www.spoj.com/problems/PARTY/ and I have tried a 0-1 knapsack algorithm that remembers its picks. Is this the correct algorithm to use in this situation and is it implemented correctly?

My Code:

#include <iostream>
#include <algorithm>
using namespace std;

int party(int nItems, int budget, int costs[], int fun[], int& tCost) {
	int matrix[101][501]={0}, picks[101][501]={0};
	for(int i=1; i<=nItems; ++i) {
		for(int j=0; j<=budget; ++j) {
			if(costs[i-1]<=j) {
				matrix[i][j]=max(matrix[i-1][j], fun[i-1]+matrix[i-1][j-costs[i-1]]);
				if(fun[i-1]+matrix[i-1][j-costs[i-1]]>(matrix[i-1][j])) picks[i][j]=1;
				else picks[i][j]=-1;
			}
			else {
				picks[i][j]=-1;
				matrix[i][j]=matrix[i-1][j];
			}
		}
	}
	tCost=0;
	int items=nItems, tbud=budget;
	while(items>0) {
		if(picks[items][tbud]==1) {
			tCost+=costs[items-1];
			--items; tbud-=costs[items];
		} else --items;
	}
	
	return(matrix[nItems][budget]);
}


int main() {
	int budget, nItems;
	cin>>budget>>nItems;
	while(budget!=0 || nItems!=0) {
		if(budget==0 || nItems==0) cout<<"0 0\n";
		int cost[nItems], fun[nItems], tCost, tFun;
		for(int i=0; i<nItems; ++i) cin>>cost[i]>>fun[i];
		tFun=party(nItems, budget, cost, fun, tCost);
		cout<<tCost<<' '<<tFun<<'\n';
		cin>>budget>>nItems;
	}
}

[Script Coder]

^bump^

[JLBorges]

> Is this the correct algorithm to use in this situation

Yes.

> is it implemented correctly?

Seems to be, at a cursory glance.

Check it out with the algorithm here: http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Dynamic/knapsackdyn.htm

[Script Coder]

Compared it, seems to be the exact same thing, except mine adds a backtracking feature which I learnt from here: http://www.programminglogic.com/knapsack-problem-dynamic-programming-algorithm/

Yet the judge still says incorrect?

[JLBorges]

> Yet the judge still says incorrect?

Test your code with a few simple test cases of your own.

[cire]

On line 37, you output "0 0\n" for the input that marks the end of input (for which you should output nothing.) And, then again you'll output it on line 41 in the same loop iteration. I just wonder if that unexpected output may be causing the judge to flag runs as wrong answers.

[Script Coder]

@cire, does the while condition not catch the outputting of end of input characters? but thank you for noticing that I could still print "0 0\n" twice.

[cire]

No, no. You're right. It does terminate the loop correctly. I guess line 37 threw me off, because it can't ever be true. I didn't take the loop condition into account at all there.