SHARE
TWEET

Untitled

a guest May 21st, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. 'use strict';
  2.  
  3. class Item {
  4.     /**
  5.      * @param {number} weight
  6.      * @param {number} value
  7.      * @param {?string=} [label]
  8.      */
  9.     constructor(weight, value, label) {
  10.         this.weight = weight;
  11.         this.value = value;
  12.         this.label = label;
  13.     }
  14.  
  15.     /**
  16.      * @returns {number}
  17.      */
  18.     get valuePerWeight() {
  19.         return this.value / this.weight;
  20.     }
  21. };
  22.  
  23. class Node {
  24.     /**
  25.      * @param {[Item]} items
  26.      * @param {number} weightAvail
  27.      * @param {number} valueBase
  28.      */
  29.     constructor(items, weightAvail, valueBase) {
  30.         this.items = items;
  31.         this.valueBase = valueBase;
  32.         this.weightTotal = weightAvail;
  33.         this.counts = new Array(items.length).fill(0);
  34.  
  35.         let upperBound = valueBase, lowerBound = valueBase, branchIdx = -1;
  36.  
  37.         for (let i = 0; i < items.length; ++i) {
  38.             const currentWeight = items[i].weight;
  39.             if (weightAvail < currentWeight) {
  40.                 this.counts[i] = weightAvail / currentWeight;
  41.                 upperBound = lowerBound + this.counts[i] * items[i].value;
  42.                 branchIdx = i;
  43.                 break;
  44.             }
  45.             this.counts[i] = 1;
  46.             weightAvail -= currentWeight;
  47.  
  48.             lowerBound += items[i].value;
  49.         }
  50.  
  51.         this.lowerBound = lowerBound;
  52.         this.upperBound = upperBound < lowerBound ? lowerBound : upperBound;
  53.         this.branchIdx = branchIdx;
  54.     }
  55. };
  56.  
  57. /**
  58.  * @param {Node} node
  59.  */
  60. const bounds = function(node) {
  61.     return [node.lowerBound, node.upperBound];
  62. };
  63.  
  64. /**
  65.  * @param {Node} node
  66.  */
  67. const branch = function(node) {
  68.     const itemsLeft = node.items.slice(0); // clone
  69.     itemsLeft.splice(node.branchIdx, 1);
  70.    
  71.     if (itemsLeft.length !== 0) {
  72.         let result = [
  73.             new Node(itemsLeft, node.weightTotal, node.valueBase),
  74.             new Node(itemsLeft, node.weightTotal - node.items[node.branchIdx].weight, node.valueBase + node.items[node.branchIdx].value),
  75.         ];
  76.         return result;
  77.     }
  78.  
  79.     return [];
  80. };
  81.  
  82. class BnB {
  83.     /**
  84.      * @param {function(TNode) : [TNode]} branch
  85.      * @param {function(TNode) : [number]} bounds
  86.      * @template TNode
  87.      */
  88.     constructor(branch, bounds) {
  89.         this.branch = branch;
  90.         this.bounds = bounds;
  91.     }
  92.  
  93.     /**
  94.      * @param {TNode} rootNode
  95.      */
  96.     solve(rootNode) {
  97.         let [lowerBound, upperBound] = this.bounds(rootNode);
  98.         let bestLowerBound = lowerBound,
  99.             bestUpperBound = upperBound;
  100.         let bestNode = rootNode;
  101.  
  102.         let queue = [rootNode];
  103.         while (queue.length > 0) {
  104.             const currentNode = queue.pop();
  105.             const childNodes = this.branch(currentNode);
  106.             console.log(JSON.stringify(childNodes));
  107.             for (let i = 0; i < childNodes.length; ++i) {
  108.                 const childNode = childNodes[i];
  109.                 const [lowerBound, upperBound] = this.bounds(childNode);
  110.                 if (lowerBound >= bestLowerBound) {
  111.                     bestLowerBound = lowerBound;
  112.                     bestNode = childNode;
  113.                 }
  114.                 /// todo: check condition (< or <=)
  115.                 if (upperBound < bestLowerBound) {
  116.                     // skip
  117.                     continue;
  118.                 }
  119.                 if (lowerBound >= upperBound) {
  120.                     break;
  121.                 }
  122.  
  123.                 queue.push(childNode);
  124.             }
  125.         }
  126.  
  127.         return bestNode;
  128.     }
  129. };
  130.  
  131. // const items = [
  132. //     new Item(25, 200),
  133. //     new Item(30, 300),
  134. //     new Item(50, 250),
  135. //     new Item(10, 320),
  136. //     new Item(60, 180),
  137. // ]
  138. const items = [
  139.     new Item(9, 150),
  140.     new Item(13, 35),
  141.     new Item(153, 200),
  142.     new Item(50, 160),
  143.     new Item(15, 60),
  144.     new Item(68, 45),
  145.     new Item(27, 60),
  146.     new Item(39, 40),
  147.     new Item(23, 30),
  148.     new Item(52, 10),
  149.     new Item(11, 70),
  150.     new Item(32, 30),
  151.     new Item(24, 15),
  152.     new Item(48, 10),
  153.     new Item(73, 40),
  154.     new Item(42, 70),
  155.     new Item(43, 75),
  156.     new Item(22, 80),
  157.     new Item(7, 20),
  158.     new Item(18, 12),
  159.     new Item(4, 50),
  160.     new Item(30, 10),
  161. ]
  162. .sort((a, b) => b.valuePerWeight - a.valuePerWeight);
  163.  
  164. const rootNode = new Node(items, 400, 0);
  165. const bnb = new BnB(branch, bounds);
  166.  
  167. const resultNode = bnb.solve(rootNode);
  168. console.log(JSON.stringify(resultNode));
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top