Most favorite bug in HW1 was in problem 4. If space==0, you could skip the recursive
call. But that
doesn't imply, as many people thought, that you then could simply do nothing.
Wrong:
for (int i = 0; i < items.length; i++)
{
int space = cap - items[i].getSize();
if (space > 0)
{
int t = items[i].getValue() + knap(space, items);
if (t > max)
max = t; // Found something better than best
}
else if (space == 0)
{
break;
}
}
The output results should have also made you suspicious, if you did it like this.
Right:
int t = 0;
for (int i = 0; i < items.length; i++)
{
int space = cap - items[i].getSize();
if (space > 0)
{
t = items[i].getValue() + knap(space, items);
}
else if (space == 0)
{
// there is still exactly enough space for this item
// but we can skip the recursive call
t = items[i].getValue();
}
if (t > max)
{
max = t;
}
}
Hans
