Choose Scenes for a Movie

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].

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)