Programmazione ACM Domanda

Question

Sto cercando di risolvere un problema di programmazione per la pratica di una competizione di domani, e ho pensato che forse questo sarebbe stato un buon posto per chiedere come affrontarlo. Il problema è il primo su questo sito: http://www.cs.rit.edu/~icpc/questions/2010/Oswego_2010.pdf

Le domande frequenti su questo sito citano algoritmi e concetti della struttura dati e modelli di progettazione, quindi credo che chiedere come affrontare questo problema non sia fuori tema. Ecco cosa ho finora (non molto). Non capisco come risolverlo.

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

Questo sembra un problema di programmazione dinamica a prima vista.

Fondamentalmente, abbiamo una funzione f (N, K) = il numero di bannas portati a casa con K disponibili bannas e le prime N monkeys.

Chiaramente f (0, K) = 0 e f (N, 0) = 0

Poi tutto quello che fare è capire il valore di f (n, k). Si dovrebbe fare in modo prendendo il massimo su due casi:

1. La scimmia non prendere un bannana f (n, k) = f (n-1, k), dal momento che la scimmia non fa nulla si tratta solo di come lui non c'è
2. la scimmia prende il bannana f (n, k) = f (n-1, k - forza) + resistenza - roba scimmia mangia

Riempire un tavolo con il nostro uso Memoizzazione questa logica e quindi determinare f (N, K) e hai la tua risposta.

Answer 2

questa domanda può essere ridotta a uno zaino 0/1 che è di per sé un algoritmo DP ben noto. Ma qui invece di valore hai capacità - Spuntini.

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

}