ACM编程问题

Question

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

这个网站上的FAQ提到了算法和数据结构的概念，以及设计模式，所以我猜询问如何处理这个问题并不离题。这是我到目前为止所拥有的(不多)。我不知道如何解决这个问题。

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-
3. )+力量材料猴子吃

用这个逻辑填充一个表格，然后确定f(N，K)，你就得到了答案。

Answer 2

这个问题可以归结为一个0/1背包问题，它本身就是一个众所周知的DP算法。但在这里，你拥有的不是价值，而是能力--零食。

Answer 3

#include <iostream>
using namespace std;
main(){
int totalwight,numberapes;
//cout<<"Enter The total weight of bananas available to lug home : ";
cin>>totalwight;
//cout<<"Enter The number of apes : ";
cin>>numberapes;
int *capacity = new int [numberapes];
int *tcapacity = new int [numberapes];
int *snackloss = new int [numberapes];
int *pos = new int [numberapes];
int *tpos = new int [numberapes];
for (int i=0 ; i<numberapes ; i++){
     pos[i]=i+1;
     tpos[i]=0;
}

for (int i=0 ; i<numberapes ; i++){
   // cout<<"Enter How many monkey # "<<i+1<<" carrying capacity : ";
    cin>>capacity[i];
    tcapacity[i]=capacity[i];
    //cout<<"Enter How many snack loss of monkey # "<<i+1<<" : ";
    cin>>snackloss[i];
}
int *arr = new int [numberapes];
for (int i=0 ; i<numberapes ; i++)
    arr[i] = capacity[i] - snackloss[i];
    int temp;
for (int i=0 ; i<numberapes ; i++)
    for (int j=0 ; j<i ; j++)
        if (arr[i] > arr[j]){
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            temp = tcapacity[i];
            tcapacity[i] = tcapacity[j];
            tcapacity[j] = temp;
            temp = pos[i];
            pos[i] = pos[j];
            pos[j] = temp;
        }
int *tarr = new int [numberapes];
int j=0;
for (int i=0 ; i<numberapes ; i++)
    tarr[i]=0;
for (int i=0 ; i<numberapes ; i++){
      if (arr[i] <= totalwight && tcapacity[i] <= totalwight){
            totalwight -= tcapacity[i];
            tpos[j] = pos[i];
            j++;
      }
}
for (int i=0 ; i<numberapes ; i++)
        for (int j=0 ; j<numberapes ; j++)
            if (tpos[j] > tpos[i] && tpos[i]!=0 && tpos[j]!=0){
                temp = tpos[i];
                tpos[i] = tpos[j];
                tpos[j] = temp;
            }
int t1=1,t2=0;
while (t1<=numberapes){
    if (t1 == tpos[t2]){
        cout<<"1 ";
        t2++;
    }
    else
        cout<<"0 ";
    t1++;
}

}