族序號爲大小爲X的桶的至少數

Question

尋找例子，關於如何組編號的集合劃分成大小爲X的桶數最少

例如，如果我有這樣的陣列的數字：

var myCompartments = { 4, 6, 2, 8, 6, 3, 1, 1, 4, 2, 7, 2, 8, 3, 9 }; 

，我想它們分成使用該桶的大小水桶：

var bucketSize = 12; 

我所尋找的是一個函數或算法，將這些組到bucke數最少ts匹配bucketSize，然後會給我剩下的數字（不適合）在它自己的列表中。

樣的結果，我想看到：

var buckets = [ 
    { 4, 6, 2 }, 
    { 8, 3, 1 }, 
    { 6, 4, 2 }, 
    { 9, 3 } 
]; 

var leftovers = {1, 7, 2, 8 }; 

如果能類似樣本的結果，將是巨大的輸出。 「剩餘」列表中最少的項目數量越多越好。

我至今僅僅是剛剛通過收集循環並增加了一個桶，如果有房，並創建一個新的水桶，如果沒有。這是效率低下的，並以很多部分滿桶結束。我使用angularJS，所以在這裏使用了一些快捷方法：

var bucketSize = 12; 
var buckets = [ 
    { remainingCapacity: bucketSize, items: [] } 
]; 
var myCompartments = [ 
    { isAssigned: false, size: 4 }, 
    { isAssigned: false, size: 6 }, 
    { isAssigned: false, size: 2 }, 
    { isAssigned: false, size: 8 }, 
    { isAssigned: false, size: 6 }, 
    { isAssigned: false, size: 3 }, 
    { isAssigned: false, size: 1 }, 
    { isAssigned: false, size: 1 }, 
    { isAssigned: false, size: 4 }, 
    { isAssigned: false, size: 2 }, 
    { isAssigned: false, size: 7 }, 
    { isAssigned: false, size: 2 }, 
    { isAssigned: false, size: 8 }, 
    { isAssigned: false, size: 3 }, 
    { isAssigned: false, size: 9 } 
]; 

myCompartments.forEach(function(compartment) { 
    buckets.forEach(function(bucket) { 
     if (bucket.remainingCapacity >= compartment.size && !compartment.isAssigned) { 
      bucket.remainingCapacity -= compartment.size; 
      compartment.isAssigned = true; 
      bucket.items.push(compartment); 
     } 
    }); 

    // if compartment still not assigned, add to a new bucket 
    if (!compartment.isAssigned && bucketSize >= compartment.size) { 
     compartment.isAssigned = true; 
     var remainingCapacity = bucketSize - compartment.size; 
     var newBucket = { remainingCapacity: remainingCapacity, items: [] }; 
     newBucket.items.push(compartment); 
     buckets.push(newBucket); 
    } 
}); 

編輯 - 我創建了一個plunker輸出調試

Answer 1

創建桶這是不漂亮，但它的工作原理。

它通過循環數據多次，每次在試圖攪亂數組值找到分組項爲特定大小的水桶更好的秩序。

plunker

$(function() { 

    var bucketSize = 12; 
    var buckets = [{ 
    remainingCapacity: bucketSize, 
    pieces: [] 
    }]; 

    var pieces = [ 
     { isAssigned: false, size: 4 },  
     { isAssigned: false, size: 6 }, 
     { isAssigned: false, size: 2 }, 
     { isAssigned: false, size: 8 }, 
     { isAssigned: false, size: 6 }, 
     { isAssigned: false, size: 3 }, 
     { isAssigned: false, size: 1 }, 
     { isAssigned: false, size: 1 }, 
     { isAssigned: false, size: 4 }, 
     { isAssigned: false, size: 2 }, 
     { isAssigned: false, size: 7 }, 
     { isAssigned: false, size: 2 }, 
     { isAssigned: false, size: 8 }, 
     { isAssigned: false, size: 3 }, 
     { isAssigned: false, size: 9 } 
    ]; 

    var unassignedCount = pieces.length; 

    var count = 1000; 

    while (count--) { 

    shuffle(pieces); 

    var p = pieces.length; 
    var b = 0; 

    while (p--) { 

     var piece = pieces[p]; 
     b = buckets.length; 

     while (b--) { 

     var bucket = buckets[b]; 

     // add to bucket if there is room and piece is not assigned 
     if (bucket.remainingCapacity >= piece.size && !piece.isAssigned) { 
      bucket.remainingCapacity -= piece.size; 
      piece.isAssigned = true; 
      bucket.pieces.push(piece); 
     } 
     } 

     // if not assigned and not bigger than bucketSize, add to new bucket 
     if (!piece.isAssigned && piece.size <= bucketSize) { 
     var remainingCapacity = bucketSize - piece.size; 
     var newBucket = { 
      remainingCapacity: remainingCapacity, 
      pieces: [] 
     }; 
     newBucket.pieces.push(piece); 
     buckets.push(newBucket); 
     } 

     pieces.splice(p, 1); 

    } 

    b = buckets.length; 

    while (b--) { 
     var bucket = buckets[b]; 
     if (bucket.remainingCapacity > 0) { 
     p = bucket.pieces.length; 
     while (p--) { 
      var piece = bucket.pieces[p]; 
      piece.isAssigned = false; 
      pieces.push(piece); 
      bucket.pieces.splice(p, 1); 
     } 
     buckets.splice(b, 1); 
     } 

    } 

    unassignedCount = pieces.length; 

    } 


    function shuffle(array) { 
    var currentIndex = array.length, 
     temporaryValue, randomIndex; 

    // While there remain elements to shuffle... 
    while (0 !== currentIndex) { 

     // Pick a remaining element... 
     randomIndex = Math.floor(Math.random() * currentIndex); 
     currentIndex -= 1; 

     // And swap it with the current element. 
     temporaryValue = array[currentIndex]; 
     array[currentIndex] = array[randomIndex]; 
     array[randomIndex] = temporaryValue; 
    } 

    return array; 
    } 

    document.write('number of buckets: ' + buckets.length + '<br><br>'); 
    document.write('number of remaining pieces: ' + unassignedCount + '<br> <br>'); 
    buckets.forEach(function(bucket) { 
    document.write('bucket:<br>'); 
    document.write('remaining capacity: ' + bucket.remainingCapacity + '<br>'); 
    document.write('items:<br>'); 
    bucket.pieces.forEach(function(piece) { 
     document.write('size: ' + piece.size + '<br>'); 
    }); 
    document.write('<br>'); 
    }); 

    document.write('<br>leftovers: '); 
    pieces.forEach(function(piece) { 
    if (!piece.isAssigned) { 
     document.write(piece.size + ', '); 
    } 
    }); 

}); 

如果其他人有一個更優雅的解決方案，我會看到你想出很有興趣！謝謝。