java - ACM编程题

Question

我正在尝试解决一个编程问题，以便为明天的比赛进行练习，我想也许这是一个询问如何处理它的好地方。问题是本网站上的第一个问题:http://www.cs.rit.edu/~icpc/questions/2010/Oswego_2010.pdf

该网站上的常见问题解答提到了算法和数据结构概念以及设计模式，所以我想询问如何解决这个问题并没有偏离主题。这是我到目前为止所拥有的(不多)。我不明白如何解决这个问题。

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

乍一看，这像是一个动态规划问题。

基本上，我们有一个函数 f(N,K) = 给定 K 可用的香蕉和前 N 只猴子带回家的香蕉的数量。

显然 f(0,K) = 0 和 f(N,0) = 0

然后您所要做的就是计算出 f(n,k) 的值。你应该通过在两种情况下取​​最大值来做到这一点:

1. 猴子没有吃香蕉 f(n,k) = f(n-1,k)，因为猴子什么都不做，就好像他不存在一样
2. 猴子吃香蕉 f(n,k) = f(n-1, k - Strength) + strength - 猴子吃的东西

用这个逻辑填写我们使用内存的表格，然后确定 f(N,K)，您就得到了答案。