Programowanie ACM Pytanie

Question

Próbuję rozwiązać problem programowania, aby ćwiczyć jutro konkurs, i pomyślałem, że może to dobre miejsce, aby zapytać, jak się do niego zbliżyć. Problem jest pierwszy na tej stronie: http://www.cs.rit.edu/~icpc/questions/2010/Oswego_2010.pdf

Najczęściej zadawane pytania na tej stronie wymienia algorytm i koncepcje struktury danych oraz wzorce projektowe, więc myślę, że pytanie, jak podejść do tego problemu, nie jest wyłączone. Oto, co mam do tej pory (niewiele). Nie rozumiem, jak rozwiązać ten problem.

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

Na pierwszy rzut oka wygląda to na problem programowania dynamicznego.

Zasadniczo mamy funkcję f (N, K) = liczba bann przyniesionych do domu z K dostępnych bann i pierwszych N małp.

Oczywiście F (0, K) = 0 f (n, 0) = 0

którą trzeba zrobić, to zrozumieć na wartość F (n, k). Powinieneś to zrobić, biorąc maksymalnie dwa przypadki:

1. Małpa nie bierze bannana f (n, k) = f (n-1, k), ponieważ małpa nic nie robi, to tylko jakby nie istnieje
2. małpa bierze bannana f (n, k) = f (n-1, k - wytrzymałość) + wytrzymałość - rzeczy małpa zjada

Fill stolik z naszego użytku memoization tej logiki, a następnie określ f (N, K) i masz swoją odpowiedź.

Answer 2

to pytanie można zredukować do plecaka 0/1, które jest dobrze znanym algorytmem DP. Ale tutaj zamiast wartości masz Pojemności - Przekąski.

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

}