Choose Scenes for a Movie

Question

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 Knapsack¹. 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

---

_{¹ Any resemblance between the challenge's problem and actual locales is entirely coincidental.}

Answer 1

MATLAB, 100 bytes

function X=o(m,s) 
X=find(bintprog(-1*s(:,3),[s(:,2)';s(:,1)';-1*s(:,1)'],[m(2);m(1)+5;5-m(1)])==1);

The Binary Optimization problem is solved through the bintprog function, available in Matlab2013b; this function was replaced by intlinprog in newer Matlab versions.

Inputs are a vector (m), for movie constraints, and a matrix (s), for the scenes. In particular m is a two-element row vector [running_time budget], while s is a Nx3 matrix, where N is the number of the scenes and each row is made up of [running_time costs importance].

Answer 2

Python 3, 211 197 bytes

This solution brute-forces every combination of scenes starting from combinations of all scenes all the way down to combinations of just one scene, then selects the combination of scenes that has maximum importance. Brute-forcing was used as the cost in time was not particularly great, though it is definitely exponential. The output is zero-indexed.

from itertools import*
def m(t,b,s):l=len(s);r=range(l);f=lambda y,k:sum(s[q][k]for q in y);return max([j for i in r for j in combinations(r,l-i)if t-6<f(j,0)<t+6and f(j,1)<=b],key=lambda n:f(n,2))

Ungolfing:

import itertools
def movie_scenes(time, budget, scenes):
    length = len(s)
    r = range(length)
    f = lambda film_list, index: sum(scenes[q][index]for q in film_list)
    importance = 0
    possible_films = []
    for num_scenes in r:
        for film in itertools.combinations(r, num_scenes):
            run_time = f(film, 0)
            cost = f(film, 1)
            if time-6 < run_time < time+6 and cost <= budget:
                possible_films.append(film)
    return max(possible_films, key = lambda film: f(film, 2)

Answer 3

Ruby, 172 166 165 bytes

I should really start checking if the Ruby versions of my Python answers are golfier before posting those Python answers. At any rate, this is the same brute-force approach to optimization as before. Any tips on golfing are welcome, including those that involve some actual optimization techniques.

->t,b,s{l=s.size;r=[*0...l];f=->y,k{y.reduce(0){|z,q|z+s[q][k]}};v=[];r.map{|i|r.combination(l-i).map{|j|v<<j if(t-5..t+5)===f[j,0]&&f[j,1]<=b}};v.max_by{|n|f[n,2]}}

Ungolfed:

def movie(time, budget, scenes)
  len = scenes.size
  range = [*0...len]
  f = -> y,k {y.reduce(0) {|z,q| z + s[q][k]}}
  potential_films = []
  range.map do |i|
    range.combination(len-i).map do |j|
    # len - i because range being combined must be 0..(len-1) as these are indices
    # but the number of elements in the combinations must be 1..len 
      if (time-5..time+5).include?(f[j,0]) && f[j,1] <= budget
        potential_films << j
      end
    end
  end
  return potential_films.max_by{|n|f[n,2]}
end

Answer 4

Haskell, 125 bytes

(m,n)&s=snd$maximum[(sum i,q)|q<-filter(>=0)<$>mapM(:[-1])[0..length s-1],(t,b,i)<-[unzip3$map(s!!)q],sum b<=n,abs(sum t-m)<6]

Usage example: (25,10) & [(5,2,4),(5,5,7),(7,1,3),(8,5,3),(12,3,9)] -> [0,1,4].

How it works:

let m be the running time
    n    the budget
    s    the list of scenes


    q<-filter ... s-1]                         -- loop q through the list of
                                               -- subsequences of the indices of s
                                               -- (0 based) -- details see below
                          map(s!!)q            -- extract the elements for the
                                               -- given indices                   
                    unzip3                     -- turn the list of triples
                                               -- into a triple of lists
          (t,b,i)<-[               ]           -- bind t, b and i to the lists
                                    sum b<=n   -- keep q if the sum of budgets <= n
                              abs(sum t-m)<6   -- and the time is within range
  (sum i,q)                                    -- for all leftover q make a pair
                                               -- (overall importance, q)
sum$maximum                                    -- find the maximum and drop
                                               -- overall importance


subsequence building:

                   [0..length s-1]         -- for all indices i of s
            (:[-1])                        -- make a list [i,-1]
        mapM                               -- and make the cartesian product
                                           -- e.g. [0,1] -> [[0,-1],[1,-1]] ->
                                           -- [[0,1],[0,-1],[-1,1],[-1,-1]]
filter(>=0)<$>                             -- drop all -1
                                           -- -> [[0,1],[0],[1],[]]

Found the subsequence trick a while ago in an answer of @xnor. It's shorter than subsequence which requires import Data.List.