Motxilla “Sluggish”

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

Informació del problema

Autoria: Unknown
Traducció: José Luis Balcázar

Generació: 2026-03-27T09:45:51.735Z