this is a bit similar to the knapsack problem. First of all, the packet capacity is 100, that is, credits < = 100 . Secondly, the Sum (points) of all the data obtained is the largest. These two points alone are very similar to the backpack problem.
The
knapsack problem is described as follows:
there is a knapsack with a backpack capacity of code 150 . There are seven items that can be divided into any size. It is required to maximize the total value of the items in the backpack as much as possible, but not more than the total capacity.
The greedy algorithm is used to solve the knapsack problem, in which the greedy strategy is to select the item with the greatest value per unit weight each time.
the greedy strategy here is to select the largest record in units credits points each time, that is, the largest record in points / credits .
need to pay attention to some conditions in the selection process:
- A record can only be selected once
- same
Team the number of selections is less than or equal to 7
- restrictions for each
position
- the number of elections reaches 11, or
credits reaches 100, then stop
- if
credits reaches 100 first, consider a replacement strategy.
add:
it seems that greed doesn't work. Think about it in a different way and consider it backtracking:
first, all records are sorted in points reverse order to build a search space tree with a height of 11. So the original problem becomes the problem of the best path to search the tree. Each time you select the largest record of points , when you search down, you can drop unnecessary branches according to the condition Filter. The following conditions must be met for each search step:
- the same record cannot be searched twice.
The number of - same
Team selections is less than or equal to 7.
- limits for each
position .
- for the selected record
Sum (points) < = 100 .
once the above conditions are not met on the search path, then backtrack to another branch to continue the search. So the whole process is a recursive process.
add:
is implemented with the backtracking algorithm, and the code is placed in github . After a simple test with several test cases, all of them are correct, and the efficiency is not very high. Optimize it yourself. Here is my output:
:
1 56 9.0 1 1
2 54 9.1 2 1
3 35 8.0 2 2
4 32 8.0 3 1
5 20 8.5 1 2
6 18 9.0 3 2
7 16 9.1 2 2
8 15 8.0 3 2
9 13 7.0 3 1
10 10 8.5 4 2
11 7 9.0 4 2
12 5 8.0 2 1
13 4 7.0 3 1
14 3 8.5 4 1
15 2 9.0 3 1
16 1 8.5 4 2
17 0 9.0 3 2
18 0 8.5 4 1
19 0 9.0 3 2
20 0 8.5 4 1
21 0 9.0 3 1
22 0 8.5 4 2
:
1 56 9.0 1 1
2 54 9.1 2 1
3 35 8.0 2 2
4 32 8.0 3 1
6 18 9.0 3 2
7 16 9.1 2 2
8 15 8.0 3 2
10 10 8.5 4 2
11 7 9.0 4 2
12 5 8.0 2 1
14 3 8.5 4 1
sumPoints:251, sumCredits:94.20,
position-1 picked(1): 1 , position-2 picked(3-5): 4 , position-3 picked(1-3): 3 , position-4 picked(3-5): 3
team picked(less than 7):{1=5, 2=6}
if correct, please adopt
