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

© Jutge.org, 2006–2026.
https://jutge.org
