java – ACM编程问题

前端之家收集整理的这篇文章主要介绍了java – ACM编程问题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

我正在努力解决一个编程问题,为明天的比赛练习,我想也许这将是一个讨论如何接近它的好地方.问题是本网站上的第一个问题: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);
    }
}
最佳答案
这看起来像一个动态编程问题乍一看.

基本上,我们有一个函数f(N,K)=给予K的bannas和前N只猴子带回家的bannas数量.

显然f(0,K)= 0并且f(N,0)= 0

然后你所要做的就是找出f(n,k)的值.您应该通过最多超过两个案例来做到这一点:

>猴子不接受bannana f(n,k)= f(n-1,k),因为猴子什么都不做,就像他不在那里一样
>猴子采取bannana f(n,k – 力量)力量 – 东西吃猴子

填写表格,我们使用这个逻辑使用memoization,然后确定f(N,K),你就得到了你的答案.

猜你在找的Java相关文章