Motxilla "sluggish" X59240

Statement

Considerem el problema clàssic de la motxilla, en la seva variant 0/1; això vol dir que cada objecte es pren enter per posar-lo a la motxilla, exactament una vegada, o es deixa completament a fora.

Més precisament, ens donen un límit de pes $limw$ i una seqüència de $n$ objectes consistent en el pes i el valor de cada objecte, on $n$ es un enter no negatiu i tots els altres valors son enters positius. Les solucions son subconjunts (més aviat, subseqüències) d’objectes, de manera que la suma dels seus pesos sigui com a molt $limw$ i la suma dels seus valors sigui com més elevada millor. S’ha de retornar una solució que ho acompleixi.

Així, se’t demana escriure una funció $knapsack(weights, values, n, limw)$ que retorni una llista d’enters més petits que $n$ , corresponent a objectes dels quals la suma dels pesos és com a molt $limw$ i la suma dels valors es la més alta possible.

Observacions

1/ Els primers dos paràmetres de la funció són seqüències d’enters positius, pes i valor de cadascú dels $n$ objectes.

2/ Nota que poden haver-hi casos en què la solució és una llista buida, quan no hi ha cap solució millor (recorda que la suma d’una llista buida és zero).

3/ De vegades, hi haurà més d’una solució: la teva funció pot retornar qualsevol solució que acompleixi les condicions donades.

4/ La disponibilitat de temps per aquest problema és prou suau i es poden acceptar àdhuc solucions prou ineficients. D’aquí l’adjectiu “sluggish”.

Sample session

>>> weights =  [7, 8, 3]
>>> values =  [3000, 4000, 2000]
>>> print(sum(values[obj] for obj in knapsack(weights, values, 3, 10)))
5000
>>> weights =  [7, 8, 3]
>>> values =  [3000, 6000, 2000]
>>> print(sum(values[obj] for obj in knapsack(weights, values, 3, 10)))
6000
>>> weights =  [1, 1, 1, 1]
>>> values =  [3, 5, 7, 7]
>>> print(sum(values[obj] for obj in knapsack(weights, values, 4, 2)))
14

Information

Author: José Luis Balcázar
Language: Catalan
Translator: José Luis Balcázar
Original language: English
Other languages: English
Official solutions: Python
User solutions: Python