introduction

Enfin, la société de cinéma finance votre film. Ils vous ont donné un budget maximum et ils ont également défini la durée de votre film.

Vous pouvez maintenant commencer par la pré-production. Vous avez déjà prévu un tas de scènes, mais toutes ne rentreront pas dans le budget et le film deviendrait bien trop long aussi. Vous savez cependant l'importance de chaque scène. Votre objectif est de choisir des scènes, que le film ne va pas être trop cher, trop long et médiocre.

Contribution

Vous obtenez le running timeet budgetle studio a approuvé:

[25, 10]

Vous avez la liste des scènes , y compris running time, costset importancepour chacun d'eux:

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

Si les tableaux ne fonctionnent pas pour vous, choisissez un autre format d'entrée qui vous convient le mieux. Les temps sont en minutes. Le budget et les coûts sont en millions de devises aléatoires. L'importance va de [1–9]. Tous les nombres sont des entiers.

Production

Sortez la liste des scènes à inclure dans le film dans la mesure où:

• La somme de importanceest maximisée.
• Les coûts ne dépassent pas le budget.
• La durée se situe dans une plage de ± 5 minutes de la durée de fonctionnement approuvée.

L'ordre des scènes est sans importance et n'a pas besoin d'être conservé.

Vous pouvez sortir une liste de nombres ou un tableau. Votre sortie peut avoir un index zéro ou un:

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

Il peut être possible que plusieurs solutions s'appliquent à une entrée donnée. Il vous suffit d'en trouver un.

Contraintes

• Les scènes ne peuvent pas être raccourcies ni moins chères.
• Chaque scène ne peut être incluse qu'une seule fois.

Exigences

• Votre programme doit se terminer dans le temps de la durée réelle du film.
• L'entrée est acceptée à partir des STDINarguments de ligne de commande, en tant que paramètres de fonction ou de l'équivalent le plus proche.
• Vous pouvez écrire un programme ou une fonction. S'il s'agit d'une fonction anonyme, veuillez inclure un exemple de la façon de l'invoquer.
• C'est le code-golf, donc la réponse la plus courte en octets gagne.
• Les failles standard ne sont pas autorisées.

Films

Votre premier film est un documentaire sur une petite ville d'Allemagne appelée Knapsack ¹ . Cette ville a été réinstallée en raison de contraintes environnementales dans les années 70:

Movie: [25, 10]

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

Solution possible avec temps d'exécution 22, budget 10et importance de 20:

0, 1, 4

Votre prochain projet est un épisode 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],
]

Solution possible avec temps d'exécution 40, budget 24et importance de 31:

0, 1, 2, 3, 4

Enfin, voici les scènes d'un film où " M. McConaughey voyage dans une galaxie lointaine pour découvrir que Matt Damon est arrivé en premier. ":

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

Solution possible avec temps d'exécution 169, budget 165et importance de 133:

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

_{¹ Toute ressemblance entre le problème du défi et les paramètres régionaux réels est entièrement une coïncidence.}

MATLAB, 100 octets

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

Le problème d'optimisation binaire est résolu grâce à la fonction bintprog , disponible dans Matlab2013b; cette fonction a été remplacée par intlinprog dans les nouvelles versions de Matlab.

Les entrées sont un vecteur (m), pour les contraintes de film, et une matrice (s), pour les scènes. En particulier, m est un vecteur de lignes à deux éléments [budget de temps d'exécution], tandis que s est une matrice Nx3, où N est le nombre de scènes et chaque ligne est composée de [importance des coûts de fonctionnement].

Python 3, 211 197 octets

Cette solution force toutes les combinaisons de scènes à partir de combinaisons de toutes les scènes jusqu'aux combinaisons d'une seule scène, puis sélectionne la combinaison de scènes qui a une importance maximale. Le forçage brutal a été utilisé car le coût dans le temps n'était pas particulièrement élevé, bien qu'il soit définitivement exponentiel. La sortie est indexée zéro.

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)

Haskell, 125 octets

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

Exemple d'utilisation: (25,10) & [(5,2,4),(5,5,7),(7,1,3),(8,5,3),(12,3,9)]-> [0,1,4].

Comment ça fonctionne:

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

J'ai trouvé l'astuce de sous-séquence il y a quelque temps dans une réponse de @xnor. C'est plus court que subsequencece qui nécessite import Data.List.

Rubis, 172 166 165 octets

Je devrais vraiment commencer à vérifier si les versions Ruby de mes réponses Python sont plus efficaces avant de publier ces réponses Python. Quoi qu'il en soit, il s'agit de la même approche d'optimisation par force brute qu'auparavant. Tous les conseils sur le golf sont les bienvenus, y compris ceux qui impliquent des techniques d'optimisation réelles.

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

Non 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