ACM編程問題

我試圖解決一個編程問題，爲明天的比賽練習，我想也許這將是一個問好如何接近它的好地方。問題是這個網站上的第一個問題：http://www.cs.rit.edu/~icpc/questions/2010/Oswego_2010.pdf ACM編程問題

本網站上的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); 
    } 
}

來源

2011-09-30 Pat Needham

一個極壞的問題描述：我沒有找到最佳的香蕉帶回家量的話。所以，當你逐字解釋時，你只需要一個「包裝」的猿，可以攜帶確切數量的可用香蕉。還有一個非常典型的ACM問題，因爲它們沒有指示數字的大小（例如N爲數十，數千，數百萬或甚至更大的數量級）。 – flolo

這看起來像是一個動態編程問題乍一看。

基本上，我們有一個函數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）= F（N-1，K - 強度）+力量 - 東西吃猴

填寫表格我們使用記憶化與這個邏輯，然後確定f（N，K），你已經得到了你的答案。

來源

2011-09-30 02:01:53

您的解決方案是錯誤的。它沒有考慮到只有最大數量的香蕉可供選擇，不能超過所選擇的猿類可以攜帶的總和，*不管那些猴子吃什麼*。 –

@DocBrown，這就是參數k的用途，它跟蹤可用的bannanas。所以是的，我確實考慮到了這一點。（我可能做錯了，但我確實試圖考慮它）沒有這個限制，顯而易見的事情就是發送每個攜帶更多他吃的猴子。 –

好的，現在我明白了。 –

這個問題可以簡化爲一個0/1揹包，它本身就是一個衆所周知的DP算法。但在這裏，而不是價值，你有能力 - 零食。

來源

2015-11-25 09:32:57

#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++; 
}

}

來源

2016-09-23 14:56:53

回答

相關問題