java动态规划问题“以输入价格购买玩家后，总评分必须最高”

Question

Players Input Table 问题是使总评级达到最大，同时以一定价格从每个位置购买一名球员。例如，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-...

Answer 1

我找到了这个背包问题的一个实现，试着在你的场景中运行它。 这对你有帮助

/**

 ** 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);

    }

}