Вопрос по программированию ACM

ProgramBox

Вопрос по программированию ACM

Post author:admin
Запись опубликована:11 марта, 2023
Post category:Вопросы по программированию

#java

Вопрос:

Я пытаюсь решить проблему программирования, чтобы попрактиковаться в завтрашнем соревновании, и я подумал, что, возможно, это было бы хорошим местом, чтобы спросить, как к этому подойти. Проблема является первой на этом сайте: http://www.cs.rit.edu /~icpc/вопросы/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);
    }
}

1. Описание очень плохой проблемы: я не нашел ни слова об оптимизации количества бананов, принесенных домой. Поэтому, когда вы интерпретируете его дословно, вам просто нужна «упаковка» apes, которая может содержать точное количество доступных бананов. Также очень нетипичный вопрос ACM, поскольку в них нет указания на размер чисел (например, N в порядке десятков, тысяч, миллионов или даже больше).

Ответ №1:

На первый взгляд это похоже на проблему динамического программирования.

В принципе, у нас есть функция f (N, K) = количество банн, принесенных домой, учитывая K доступных банн и первых N обезьян.

Очевидно, что f(0, K) = 0 и f (N, 0) = 0

Тогда все, что вам нужно сделать, это вычислить значение f(n, k) . Вы должны сделать это, взяв максимум за два случая:

Обезьяна не принимает bannana f(n, k) = f (n-1,k), поскольку обезьяна ничего не делает, это похоже на то, что его там нет
Обезьяна берет баннану f(n, k) = f (n-1, k — Сила) сила — то, что ест обезьяна

Заполните таблицу, в которой мы используем memoization, с помощью этой логики, а затем определите f(N,K), и вы получите свой ответ.

1. Ваше решение неверно. При этом не учитывается, что доступно только максимальное количество бананов, которое не может быть превышено суммой того, что могут нести выбранные обезьяны, независимо от того, что едят эти обезьяны .

2. @DocBrown, для этого и нужен параметр k, он отслеживает доступные баннеры. Так что да, я принимаю это во внимание. (Возможно, я сделал это неправильно, но я попытался принять это во внимание) Без этого ограничения очевидным было бы отправить каждую обезьяну, которая несет больше, чем ест.

Ответ №2:

этот вопрос можно свести к ранцу 0/1, который сам по себе является хорошо известным алгоритмом DP. Но здесь вместо ценности у вас есть Емкости — Закуски.

Ответ №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 amp;amp; 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] amp;amp; tpos[i]!=0 amp;amp; 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  ;
}

}

Ответ №4:

Пожалуйста, посмотрите мой ответ:

 using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;

namespace monkey
{
    class Program
    {

        static int getTotalCapacity(int[] ki, int[] indexes)
        {
            int result = 0;
            foreach (int i in indexes)
            {
                result  = ki[i];
            }
            return resu<

        }

        static int[] computeOutput(int k, int n, int[] ki, int[] wi)
        {
            // #1: Sort the input by ki - wi
            Dictionary<int, int> vi = new Dictionary<int, int>();
            for (int i = 0; i < n; i  )
            {
                vi.Add(i, ki[i] - wi[i]);
            }
            Dictionary<int, int> sorted_vi = (from entry in vi orderby entry.Value descending select entry).ToDictionary(x => x.Key, x => x.Value);

            // #2: Take elements in sequence in order to fulfill the minimum total k
            Dictionary<int, int> result = new Dictionary<int, int>();
            foreach (KeyValuePair<int, int> kv in sorted_vi)
            {
                if (ki[kv.Key]   getTotalCapacity(ki, result.Select(x=>x.Key).ToArray()) <= k)
                {
                    result.Add(kv.Key,kv.Value);
                }
            }

            // #3 Transform to output format
            int[] output = new int[n];
            foreach(KeyValuePair<int,int> kv in result){
                output[kv.Key] = 1;
            }

            return output;
        }

        static void Main(string[] args)
        {
            if (args.Length != 1)
            {
                Console.WriteLine("Usage: <prog>.exe <filepath>");
                return;
            }
            try
            {
                int k;
                int n;
                int[] ki;
                int[] wi;

                // Reading file input
                using (StreamReader fs = new StreamReader(args[0]))
                {
                    k = Convert.ToInt32(fs.ReadLine());
                    n = Convert.ToInt32(fs.ReadLine());
                    ki = new int[n];
                    wi = new int[n];
                    for (int i = 0; i < n; i  )
                    {
                        string[] line = fs.ReadLine().Split(new string[] { " " }, StringSplitOptions.RemoveEmptyEntries);
                        ki[i] = Convert.ToInt32(line[0]);
                        wi[i] = Convert.ToInt32(line[1]);
                    }
                }

                int[] output = computeOutput(k, n, ki, wi);
                Console.WriteLine(string.Join(" ", output));

            }
            catch (Exception ex)
            {
                Console.WriteLine(ex.Message);
                return;
            }
        }
    }
}