Задача динамического программирования «Общий рейтинг должен быть максимальным после покупки игроков с входной ценой» - PullRequest
Новая
       11

Задача динамического программирования «Общий рейтинг должен быть максимальным после покупки игроков с входной ценой»

0 голосов
/ 20 мая 2019

Таблица входа игроков Проблема заключается в максимальном общем рейтинге, при покупке одного игрока с каждой позиции по определенной цене.Например 29000 €.Вы можете использовать 27000 €, но не можете использовать 29001 €.

Примечание: Вы можете купить только одного игрока с каждой позиции, поэтому, если есть 6 позиций, и в каждой позиции 10 игроков, количество всех возможностей составляет 11^ 6

Все, что я вижу, это проблема ранца, но я думаю, что должно быть какое-то отличное решение этой проблемы.

Я уже пробовал алгоритм ранца, но он не работал для больших входов, таких как11 позиций и каждая позиция имеет 50 игроков для проверки. 

int DP()
{
   int price = 29000;
   int positions = 3;   // I tried this approach , it is unfinished though. 
   int players = 3;

   int ratings[][] = new int[positions][players];
   int prices[][] = new int[positions][prices];
   int K[][][] = new int[positions][price][players];

   for(int i = 0; i <= positions; i++)  
  {
      for(int j = 0; j<=players; j++)
        {
           for(int w = 0; w<=price; w++)
                {
                   if(i==0||j==0||w==0)   // Base case.
                       K[i][j][w]=0;
                   else if(prices[i-1][w-1] <=w)
                       K[i][j][w] = max(ratings[i-1][j-1] + K[i-1][j-1][w-price[i-1][j-1]], K[i-1][j-1][w];
                   else
                       K[i][j][w] = K[i-1][j-1][w];
                }
        }
  }
    return K[positions][players][price];
}

Пример вывода: 

Enter the amount to spend (X): 100 000
Enter the number of the positions (N): 6 //The first N position
Enter the number of the available players for each position (K): 5
// The first K players of each position
DP results:
Total ratings : 547
Total cost: 98 925
Players:
1-Gianfranco Zola
2-Jimmy Floyd Hasselbaink
3-...
4-...

1 Ответ

0 голосов
/ 20 мая 2019

Я нашел реализацию этой проблемы с рюкзаком, попробуйте запустить ее с вашим сценарием.это поможет вам !! 

/**

 ** Java Program to Implement Knapsack Algorithm

 **/



import java.util.Scanner;



/** Class Knapsack **/

public class Knapsack

{

    public void solve(int[] wt, int[] val, int W, int N)

    {

        int NEGATIVE_INFINITY = Integer.MIN_VALUE;

        int[][] m = new int[N + 1][W + 1];

        int[][] sol = new int[N + 1][W + 1];



        for (int i = 1; i <= N; i++)

        {

            for (int j = 0; j <= W; j++)

            {

                int m1 = m[i - 1][j];

                int m2 = NEGATIVE_INFINITY; 

                if (j >= wt[i])

                    m2 = m[i - 1][j - wt[i]] + val[i];

                /** select max of m1, m2 **/

                m[i][j] = Math.max(m1, m2);

                sol[i][j] = m2 > m1 ? 1 : 0;

            }

        }        

        /** make list of what all items to finally select **/

        int[] selected = new int[N + 1];

        for (int n = N, w = W; n > 0; n--)

        {

            if (sol[n][w] != 0)

            {

                selected[n] = 1;

                w = w - wt[n];

            }

            else

                selected[n] = 0;

        }

        /** Print finally selected items **/

        System.out.println("\nItems selected : ");

        for (int i = 1; i < N + 1; i++)

            if (selected[i] == 1)

                System.out.print(i +" ");

        System.out.println();

    }

    /** Main function **/

    public static void main (String[] args) 

    {

        Scanner scan = new Scanner(System.in);

        System.out.println("Knapsack Algorithm Test\n");

        /** Make an object of Knapsack class **/

        Knapsack ks = new Knapsack();



        System.out.println("Enter number of elements ");

        int n = scan.nextInt();



        int[] wt = new int[n + 1];

        int[] val = new int[n + 1];



        System.out.println("\nEnter weight for "+ n +" elements");

        for (int i = 1; i <= n; i++)

            wt[i] = scan.nextInt();

        System.out.println("\nEnter value for "+ n +" elements");

        for (int i = 1; i <= n; i++)

            val[i] = scan.nextInt();



        System.out.println("\nEnter knapsack weight ");

        int W = scan.nextInt();



        ks.solve(wt, val, W, n);

    }

}
...