एसीएम प्रोग्रामिंग प्रश्न

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

यह पहली नज़र में गतिशील प्रोग्रामिंग समस्या की तरह दिखता है।

असल में, हमारे पास एक फ़ंक्शन एफ (एन, के) = बन्नों की संख्या है जो घर के लिए उपलब्ध बन्ना और पहले एन बंदरों को लाया गया है।

जाहिर च (0, कश्मीर) = 0 और च (एन, 0) = 0

फिर तुम सब करने की है च (एन, ट) के मूल्य में यह पता लगाने की है।

1. बंदर, एक bannana F (n, k) = च नहीं ले करता है (n-1, ट) के बाद से बंदर कुछ नहीं करता है यह सिर्फ है: आप दो मामले पर अधिकतम लेने के द्वारा ऐसा करना चाहिए जैसे वह वहाँ
2. नहीं है बंदर bannana F (n, k) = च लेता है (n-1, कश्मीर - शक्ति) + शक्ति - सामान बंदर

खाती है के साथ एक मेज हमारे उपयोग Memoization भरें यह तर्क और फिर एफ (एन, के) निर्धारित करें और आपको अपना जवाब मिल गया है।

Answer 2

इस प्रश्न को 0/1 knapsack तक घटाया जा सकता है जो स्वयं एक प्रसिद्ध डीपी एल्गोरिदम है। लेकिन यहां मूल्य के बजाय आपके पास क्षमताएं हैं - स्नैक्स।

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

}