Это похоже на knapsack «вариацию»: мы берем элемент или нет.
рекурсивный подход
для заданного v (каждый элемент представляет собой блок),и текущую общую ширину s
мы можем рассмотреть рекурсивную функцию def recurse(v, s)
, которая:
- , если v пусто или s == 0(мы не можем заполнить больше ящиков)
return {s:0, cost:0} - вынуть первый элемент
v как (w,h,cost) (Вы определили стоимость как w * h) три варианта:
- без учета текущего поля
p1 = recurse(v, s)
- s - w> = 0:
r = recurse(v, s-w)
p2 = {
s: w+r.s,
c: cost + r.cost
}
s - h> =0:
r = recurse(v, s-h)
p3 = {
s: h+r.s,
c: cost + r.cost
}
и который возвращает минимальное p_i (согласно p_i.s сначала, затем p_i.cost), которое вы бы назвали с помощью recurse(v, 16)
динамический подход
Мы можем инициализировать структуру из всех возможных сумм
Простейшим является массив размером 17 (для суммы == 0 до 16) (см. Далееas layer)
Каждый элемент слоя содержит: минимальный cost, boxes используется для достижения этой стоимости
initialize the layer according to the boxes
foreach box(w,h,cost) of v
nextLayer = copy(layer)
//layerW is simply the idx of layerEl, aka the sum of width of layerEl.boxes
forall layerEl, layerW of the layer
if layerEl.boxes contain box
//skip that current layerEl
break
if layerEl is valid: (it is not an "empty" box due to initialization)
//we may obtain a new sum: box.w + layerEl.w
//that new sum can be compared to layer[ box.w + layerW ]
//update layer[ box.w + layerW ] only if
//* layer[ box.w + layerW ] is invalid
//* OR its cost is greater
if update:
nextLayer[ box.w + layerW ] = {
cost: box.cost + layerEl.cost,
boxes: box U layerW.boxes
}
//do the same with box.h
layer = nextLayer
//got it: layer[16]
в конце, мы использовали все поля (или нет) v, и мы можем просто взять 16-й слой слоя
ниже - стандартная рекурсия (с памяткой (cache));и дп реализуют
///13132973/polnaya-upakovka-paketov
//==> find all sums which give width, and take the lowest weight
var v = [[2,6],[6,4],[4,4],[6,3],[1,12],[7,3],[3,5],[1,2]];
var costs= [12, 24, 16, 18, 12, 21, 15, 10];
var maxW = 16;
var cache = {};
function rec(v, depth, w){
if(depth == -1 || w == 0)return {w:0, cost: 0, v:[]};
let id = depth+'-'+w;
if(cache[id])return cache[id];
//don't take current
let best = rec(v, depth-1, w);
let [a,b] = v[depth];
let cost = costs[depth];
let sorted = [a,b].map(el=>{
if( w - el >= 0){
//we can take el
let res = rec(v, depth-1, w-el);
return {
w: el + res.w,
cost: cost + res.cost,
v: [el].concat(res.v)
}
}
}).filter(x=>!!x);
if(sorted.length){
//minimize w, and for equal w, select the minimal weight
best = sorted.concat(best).sort((a,b)=>{
if(a.w < b.w){
return 1;
}
if(a.w > b.w){
return -1;
}
return a.cost - b.cost;
})[0];
}
cache[id] = best;
return best;
}
console.log(rec(v, v.length-1, maxW));
function dp(){
//make all sums up to width
//for an indentical width, select the one with lowest weight
//ith idx in layer means width==i,
//ith element holds the optimal "combination" (minimal cost) leading to that width
let layer = new Array(maxW+1).fill(0).map(w=>Object.assign({},{cost:1000}));
v.forEach((elems,i)=>{
let cost = costs[i];
elems.forEach(el=>{
if(layer[el].cost == 1000 || layer[el].cost > cost){
layer[el] = {cost: cost, s:new Set([el]), indices:new Set([i])}
}
})
});
for(var i = v.length-1; i>=0; --i){
let [a,b] = v[i];
let cost = costs[i];
let next = layer.slice(0);
layer.forEach((c,w)=>{
//the current (width)sum is not yet valid, hammer time
if(c.cost == 1000)return;
//you cannot use yourself twice (v[i] + initialization)
if(c.indices.has(i)){return}
[a,b].forEach(el=>{
if(w + el > maxW){
return;
}
let best = layer[w+el];
//lhs sum is valid, and can override an invalid sum (layer[w+el].cost==1000)
if( cost + layer[w].cost < layer[w+el].cost || layer[w+el].cost==1000){
best = {cost: cost + layer[w].cost,
s:new Set([el].concat([...layer[w].s])),
indices: new Set([i].concat([...layer[w].indices]))
}
}
next[w + el] = best;
});
});
layer = next;
}
return layer[maxW];
}
let res = dp();
console.log({cost:res.cost, v:[...res.s], indices:[...res.indices]});