Pregunta de programación ACM

Question

Estoy tratando de resolver un problema de programación para practicar para una competencia mañana, y pensé que tal vez este sería un buen lugar para preguntar cómo abordarlo. El problema es el primero en este sitio: http://www.cs.rit.edu/~icpc/questions/2010/Oswego_2010.pdf

Las preguntas frecuentes en este sitio mencionan conceptos de estructura de datos y Algoritmo, y patrones de diseño, así que supongo que preguntar cómo abordar este problema no está fuera de tema. Esto es lo que tengo hasta ahora (no mucho). No entiendo cómo resolver esto.

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

Parece un problema de programación dinámica a primera vista.

Básicamente, tenemos una función f (N, K) = la cantidad de bannas traídas a casa dado K disponibles bannas y los primeros N monos.

Claramente f (0, K) = 0 y f (N, 0) = 0

Entonces todo lo que tiene que hacer es averiguar el valor de f (n, k). Debe hacerlo tomando el máximo sobre dos casos:

1. El mono no tomar un plátano f (n, k) = f (n-1, k), ya que el mono no hace nada es sólo como si él no está allí
2. el mono lleva el plátano f (n, k) = f (n-1, k - fuerza) + fuerza - mono cosas come

rellenar una tabla con nuestra memoization uso esta lógica y luego determina f (N, K) y tienes tu respuesta.

Answer 2

esta pregunta se puede reducir a una mochila 0/1, que es en sí misma un conocido algoritmo DP. Pero aquí, en lugar de valor, tienes Capacidades - Aperitivos.

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

}