Introduction
Finally the movie company is financing your film. They have given you a maximum budget and they also set the running time of your movie.
Now you can start with the pre-production. You have a bunch of scenes already planned, but not all of them will fit into the budget and the film would get way too long as well. You know however the importance of each scene. You goal is to choose scenes, that the movie is not going to be too expensive, too long and mediocre.
Input
You get the running time
and the budget
the studio has approved:
[25, 10]
You have the list of scenes including running time
, costs
and the importance
for each of them:
[ [5, 2, 4], [7, 1, 3] ]
If arrays aren't working for you, choose another input format that suits your best. Times are in minutes. Budget and costs are in millions of random currency. The importance is a range from [1–9]
. All numbers are integers.
Output
Output the list of scenes to be included into the movie in the matter that:
- The sum of
importance
is maximized. - The costs do not exceed the budget.
- The length is within a ±5 minutes range of the approved running time.
The order of scenes is unimportant and doesn't need to be preserved.
You can output a list of numbers or an array. Your output can have a zero- or a one-based index:
[0,2,5] – 0, 2, 5 – 0 2 5
[1,3,6] – 1, 3, 6 – 1 3 6
It may be possible, that multiple solutions apply to any given input. You only need to find one.
Constraints
- Scenes can't be shortened nor can they get cheaper.
- Each scene can only be included once.
Requirements
- Your program must finish in the time of the movie's actual length.
- Input is accepted from
STDIN
, command line arguments, as function parameters or from the closest equivalent. - You can write a program or a function. If it is an anonymous function, please include an example of how to invoke it.
- This is code-golf so shortest answer in bytes wins.
- Standard loopholes are disallowed.
Movies
Your first movie is a documentary about a small town in Germany called Knapsack1. This city was resettled due to environmental constraints in the 70s:
Movie: [25, 10]
Scenes: [
[5, 2, 4],
[5, 5, 7],
[7, 1, 3],
[8, 5, 3],
[12, 3, 9],
]
Possible solution with running time 22
, budget 10
and an importance of 20
:
0, 1, 4
Your next project is an episode of Fargo:
Movie: [45, 25]
Scenes: [
[2, 1, 1],
[8, 5, 9],
[10, 6, 8],
[10, 3, 6],
[10, 9, 7],
[11, 4, 3],
[19, 5, 6],
]
Possible solution with running time 40
, budget 24
and an importance of 31
:
0, 1, 2, 3, 4
Finally here are the scenes for a movie where "M. McConaughey travels to a distant galaxy only to find out that Matt Damon got there first.":
Movie: [169, 165]
Scenes: [
[5, 8, 2],
[5, 20, 6],
[6, 5, 8],
[6, 10, 3],
[7, 6, 5],
[7, 9, 4],
[7, 8, 9],
[7, 9, 5],
[8, 6, 8],
[8, 8, 8],
[8, 5, 6],
[9, 5, 6],
[9, 8, 5],
[9, 4, 6],
[9, 6, 9],
[9, 8, 6],
[9, 7, 8],
[10, 22, 4],
[10, 12, 9],
[11, 7, 9],
[11, 9, 8],
[12, 11, 5],
[15, 21, 7],
]
Possible solution with running time 169
, budget 165
and an importance of 133
:
1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22
1 Any resemblance between the challenge's problem and actual locales is entirely coincidental.