Câu hỏi lập trình ACM

Question

Tôi đang cố gắng giải quyết vấn đề lập trình để thực hành cho một cuộc thi vào ngày mai, và tôi nghĩ có lẽ đây sẽ là một nơi tốt để hỏi cách tiếp cận nó. Vấn đề là sự cố đầu tiên trên trang web này: http://www.cs.rit.edu/~icpc/questions/2010/Oswego_2010.pdf

Câu hỏi thường gặp trên trang này đề cập đến khái niệm Thuật toán và cấu trúc dữ liệu và Mẫu thiết kế, vì vậy tôi đoán cách tiếp cận vấn đề này không phải là chủ đề. Đây là những gì tôi có cho đến nay (không nhiều). Tôi không hiểu làm thế nào để giải quyết điều này.

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

Trông giống như vấn đề lập trình động ở cái nhìn đầu tiên.

Về cơ bản, chúng tôi có chức năng f (N, K) = số bannas mang về nhà cho K bannas sẵn có và N khỉ đầu tiên.

Rõ ràng f (0, K) = 0 và f (N, 0) = 0

Sau đó, tất cả các bạn phải làm là tìm ra giá trị của f (n, k). Bạn nên làm như vậy bằng cách lấy tối đa hai trường hợp:

1. Con khỉ không dùng bannana f (n, k) = f (n-1, k), vì con khỉ không làm gì cả như ông không phải là có
2. Con khỉ lấy f chuối (n, k) = f (n-1, k - Strength) + sức mạnh - thứ khỉ ăn

Điền một bảng memoization sử dụng của chúng tôi với logic này và sau đó xác định f (N, K) và bạn đã có câu trả lời của bạn.

Answer 2

câu hỏi này có thể được giảm xuống thành một gói 0/1 mà chính nó là một thuật toán DP nổi tiếng. Nhưng ở đây thay vì giá trị bạn có năng lực - Đồ ăn nhẹ.

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

}