Ici les contraintes sont différentes (par rapport aux problème d'avant):
On a une contrainte d'égalité et on minimise une somme
sous réserve que les poids sont tous positifs ET que les valeurs sont toutes supérieures à 1
On peut remarquer que pour deux combinaisons d'un même ensemble de boites qui ont la même valeur (produit de leur valeur)
alors il faut préférer celle qui a le plus petit poids
Le code peut être réutilisé de manière relativement similaire
- Code: Tout sélectionner
const boxes = {
'a': { id: 'a', value: 15, weight: 85 },
'b': { id: 'b', value: 40, weight: 60 },
'c': { id: 'c', value: 60, weight: 40 },
'd': { id: 'd', value: 10, weight: 20 }
}
const VALUE_CONSTRAINT = 600
let candidates = new Map([[0, { value: 1, weight: 0, ids: ['identitybox'] }]])
const totalWeight = Object.values(boxes).reduce((s, x) => s + x.weight, 0)
let best = {
value: 1,
weight: totalWeight + 1
}
for (const box of Object.values(boxes)) {
const next = new Map([...candidates.entries()])
for (const candidate of candidates.values()) {
// warn, int overflow
const value = candidate.value * box.value
if (value > VALUE_CONSTRAINT) {
continue
}
const weight = candidate.weight + box.weight
if (!next.has(value) || weight < next.get(value).weight) {
const betterCandidate = { value, weight, ids: [box.id, ...candidate.ids] }
if (weight < best.weight && value === VALUE_CONSTRAINT) {
console.log('improve', { weight, betterCandidate })
best = betterCandidate
}
next.set(value, betterCandidate)
}
}
candidates = next
}
/*
improve {
weight: 145,
betterCandidate: { value: 600, weight: 145, ids: [ 'b', 'a', 'identitybox' ] }
}
improve {
weight: 60,
betterCandidate: { value: 600, weight: 60, ids: [ 'd', 'c', 'identitybox' ] }
}
*/
https://jsfiddle.net/u4d1zw2L/
