Introducción

Finalmente, la compañía de películas está financiando tu película. Le han dado un presupuesto máximo y también establecen el tiempo de ejecución de su película.

Ahora puedes comenzar con la preproducción. Ya tienes un montón de escenas planeadas, pero no todas encajarán en el presupuesto y la película también durará demasiado. Sin embargo, sabes la importancia de cada escena. Tu objetivo es elegir escenas, para que la película no sea demasiado cara, demasiado larga y mediocre.

Entrada

Obtienes el running timey budgetel estudio ha aprobado:

[25, 10]

Tienes la lista de escenas incluidas running time, costsy la importancede cada una de ellas:

[ [5, 2, 4], [7, 1, 3] ]

Si las matrices no funcionan para usted, elija otro formato de entrada que se adapte mejor a usted. Los tiempos son en minutos. El presupuesto y los costos están en millones de monedas al azar. La importancia es un rango de [1–9]. Todos los números son enteros.

Salida

Imprima la lista de escenas que se incluirán en la película en el asunto que:

• La suma de importancese maximiza.
• Los costos no exceden el presupuesto.
• La duración está dentro de un rango de ± 5 minutos del tiempo de ejecución aprobado.

El orden de las escenas no es importante y no necesita ser preservado.

Puede generar una lista de números o una matriz. Su salida puede tener un índice basado en cero o en uno:

[0,2,5] – 0, 2, 5 – 0 2 5
[1,3,6] – 1, 3, 6 – 1 3 6

Es posible que se apliquen múltiples soluciones a cualquier entrada dada. Solo necesitas encontrar uno.

Restricciones

• Las escenas no se pueden acortar ni se pueden hacer más baratas.
• Cada escena solo se puede incluir una vez.

Requisitos

• Su programa debe finalizar en el momento de la duración real de la película.
• La entrada se acepta desde STDINargumentos de línea de comandos, como parámetros de función o desde el equivalente más cercano.
• Puedes escribir un programa o una función. Si es una función anónima, incluya un ejemplo de cómo invocarla.
• Este es el código de golf, por lo que la respuesta más corta en bytes gana.
• Las lagunas estándar no están permitidas.

Películas

Tu primera película es un documental sobre un pequeño pueblo en Alemania llamado Knapsack ¹ . Esta ciudad fue reasentada debido a limitaciones ambientales en los años 70:

Movie: [25, 10]

Scenes: [
    [5,  2, 4],
    [5,  5, 7],
    [7,  1, 3],
    [8,  5, 3],
    [12, 3, 9],
]

Posible solución con tiempo de ejecución 22, presupuesto 10y una importancia de 20:

0, 1, 4

Tu próximo proyecto es un episodio de 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],
]

Posible solución con tiempo de ejecución 40, presupuesto 24y una importancia de 31:

0, 1, 2, 3, 4

Finalmente, aquí están las escenas de una película en la que " M. McConaughey viaja a una galaxia distante solo para descubrir que Matt Damon llegó allí primero ":

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

Posible solución con tiempo de ejecución 169, presupuesto 165y una importancia de 133:

1, 2, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22

_{¹ Cualquier parecido entre el problema del desafío y los entornos locales reales es totalmente casual.}

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

El problema de optimización binaria se resuelve a través de la función bintprog , disponible en Matlab2013b; esta función fue reemplazada por intlinprog en las nuevas versiones de Matlab.

Las entradas son un vector (m), para restricciones de películas, y una matriz (s), para las escenas. En particular, m es un vector de fila de dos elementos [presupuesto de tiempo de ejecución], mientras que s es una matriz Nx3, donde N es el número de escenas y cada fila está compuesta por [importancia de costos de tiempo de ejecución].

Python 3, 211 197 bytes

Esta solución fuerza por fuerza bruta cada combinación de escenas, desde combinaciones de todas las escenas hasta combinaciones de una sola escena, luego selecciona la combinación de escenas que tiene la máxima importancia. Se utilizó el uso de fuerza bruta ya que el costo en el tiempo no fue particularmente grande, aunque definitivamente es exponencial. La salida está indexada a cero.

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

No golfista:

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)

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]

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

Cómo funciona:

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],[]]

Encontré el truco de subsecuencia hace un tiempo en una respuesta de @xnor. Es más corto de lo subsequenceque requiere import Data.List.

Ruby, 172 166 165 bytes

Realmente debería comenzar a verificar si las versiones de Ruby de mis respuestas de Python son más elegantes antes de publicar esas respuestas de Python. En cualquier caso, este es el mismo enfoque de optimización de fuerza bruta que antes. Cualquier consejo sobre golf es bienvenido, incluidos aquellos que involucran algunas técnicas de optimización reales.

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

Sin golf:

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