ACM Programming Question

Question

I'm trying to solve a programming problem to practice for a competition tomorrow, and I thought maybe this would be a good place to ask how to approach it. The problem is the first one on this site: http://www.cs.rit.edu/~icpc/questions/2010/Oswego_2010.pdf

The FAQ on this site mentions Algorithm and data structure concepts, and Design patterns, so I guess asking how to approach this problem isn't off topic. Here is what I have so far (not much). I don't understand how to solve this.

public class Ape
{
    public void computeOutput(int weight, int[] capacities, int[] snackLosses)
    {
        //not sure what to do
    }

    public static void main(String [] args) throws FileNotFoundException
    {
        Ape ape = new Ape();
        File file = new File(args[0]);
        Scanner in = new Scanner(file);
        int totalWeight = in.nextInt();
        int n = in.nextInt();
        int[] capacities = new int[n];
        int[] snackLosses = new int[n];

        for (int i = 0; i < n; i++)
        {
            capacities[i] = in.nextInt();
            snackLosses[i] = in.nextInt();
        }

        ape.computeOutput(totalWeight, capacities, snackLosses);
    }
}

Answer 1

This looks like a dynamic programming problem at first glance.

Basically, we have a function f(N,K) = the number of bannas brought home given K available bannas and the first N monkeys.

Clearly f(0,K) = 0 and f(N,0) = 0

Then all you have to do is figure out the value of f(n,k). You should do so by taking the maximum over two case:

1. The monkey doesn't take a bannana f(n,k) = f(n-1,k), since the monkey does nothing it is just like he isn't there
2. The monkey takes the bannana f(n,k) = f(n-1, k - Strength) + strength - stuff monkey eats

Fill a table our use memoization with this logic and then determine f(N,K) and you've got your answer.