Repository navigation
Expand file tree
/
Copy pathKnapsack.js
More file actions
196 lines (170 loc) 路 6.94 KB
/
Copy pathKnapsack.js
File metadata and controls
196 lines (170 loc) 路 6.94 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
import MergeSort from '../../sorting/merge-sort/MergeSort';
export default class Knapsack {
/**
* @param {KnapsackItem[]} possibleItems
* @param {number} weightLimit
*/
constructor(possibleItems, weightLimit) {
this.selectedItems = [];
this.weightLimit = weightLimit;
this.possibleItems = possibleItems;
}
sortPossibleItemsByWeight() {
this.possibleItems = new MergeSort({
/**
* @var KnapsackItem itemA
* @var KnapsackItem itemB
*/
compareCallback: (itemA, itemB) => {
if (itemA.weight === itemB.weight) {
return 0;
}
return itemA.weight < itemB.weight ? -1 : 1;
},
}).sort(this.possibleItems);
}
sortPossibleItemsByValue() {
this.possibleItems = new MergeSort({
/**
* @var KnapsackItem itemA
* @var KnapsackItem itemB
*/
compareCallback: (itemA, itemB) => {
if (itemA.value === itemB.value) {
return 0;
}
return itemA.value > itemB.value ? -1 : 1;
},
}).sort(this.possibleItems);
}
sortPossibleItemsByValuePerWeightRatio() {
this.possibleItems = new MergeSort({
/**
* @var KnapsackItem itemA
* @var KnapsackItem itemB
*/
compareCallback: (itemA, itemB) => {
if (itemA.valuePerWeightRatio === itemB.valuePerWeightRatio) {
return 0;
}
return itemA.valuePerWeightRatio > itemB.valuePerWeightRatio ? -1 : 1;
},
}).sort(this.possibleItems);
}
// Solve 0/1 knapsack problem
// Dynamic Programming approach.
solveZeroOneKnapsackProblem() {
// We do two sorts because in case of equal weights but different values
// we need to take the most valuable items first.
this.sortPossibleItemsByValue();
this.sortPossibleItemsByWeight();
this.selectedItems = [];
// Create knapsack values matrix.
const numberOfRows = this.possibleItems.length;
const numberOfColumns = this.weightLimit;
const knapsackMatrix = Array(numberOfRows).fill(null).map(() => {
return Array(numberOfColumns + 1).fill(null);
});
// Fill the first column with zeros since it would mean that there is
// no items we can add to knapsack in case if weight limitation is zero.
for (let itemIndex = 0; itemIndex < this.possibleItems.length; itemIndex += 1) {
knapsackMatrix[itemIndex][0] = 0;
}
// Fill the first row with max possible values we would get by just adding
// or not adding the first item to the knapsack.
for (let weightIndex = 1; weightIndex <= this.weightLimit; weightIndex += 1) {
const itemIndex = 0;
const itemWeight = this.possibleItems[itemIndex].weight;
const itemValue = this.possibleItems[itemIndex].value;
knapsackMatrix[itemIndex][weightIndex] = itemWeight <= weightIndex ? itemValue : 0;
}
// Go through combinations of how we may add items to knapsack and
// define what weight/value we would receive using Dynamic Programming
// approach.
for (let itemIndex = 1; itemIndex < this.possibleItems.length; itemIndex += 1) {
for (let weightIndex = 1; weightIndex <= this.weightLimit; weightIndex += 1) {
const currentItemWeight = this.possibleItems[itemIndex].weight;
const currentItemValue = this.possibleItems[itemIndex].value;
if (currentItemWeight > weightIndex) {
// In case if item's weight is bigger then currently allowed weight
// then we can't add it to knapsack and the max possible value we can
// gain at the moment is the max value we got for previous item.
knapsackMatrix[itemIndex][weightIndex] = knapsackMatrix[itemIndex - 1][weightIndex];
} else {
// Else we need to consider the max value we can gain at this point by adding
// current value or just by keeping the previous item for current weight.
knapsackMatrix[itemIndex][weightIndex] = Math.max(
currentItemValue + knapsackMatrix[itemIndex - 1][weightIndex - currentItemWeight],
knapsackMatrix[itemIndex - 1][weightIndex],
);
}
}
}
// Now let's trace back the knapsack matrix to see what items we're going to add
// to the knapsack.
let itemIndex = this.possibleItems.length - 1;
let weightIndex = this.weightLimit;
while (itemIndex > 0) {
const currentItem = this.possibleItems[itemIndex];
const prevItem = this.possibleItems[itemIndex - 1];
// Check if matrix value came from top (from previous item).
// In this case this would mean that we need to include previous item
// to the list of selected items.
if (
knapsackMatrix[itemIndex][weightIndex]
&& knapsackMatrix[itemIndex][weightIndex] === knapsackMatrix[itemIndex - 1][weightIndex]
) {
// Check if there are several items with the same weight but with the different values.
// We need to add highest item in the matrix that is possible to get the highest value.
const prevSumValue = knapsackMatrix[itemIndex - 1][weightIndex];
const prevPrevSumValue = knapsackMatrix[itemIndex - 2][weightIndex];
if (
!prevSumValue
|| (prevSumValue && prevPrevSumValue !== prevSumValue)
) {
this.selectedItems.push(prevItem);
}
} else if (knapsackMatrix[itemIndex - 1][weightIndex - currentItem.weight]) {
this.selectedItems.push(prevItem);
weightIndex -= currentItem.weight;
}
itemIndex -= 1;
}
}
// Solve unbounded knapsack problem.
// Greedy approach.
solveUnboundedKnapsackProblem() {
this.sortPossibleItemsByValue();
this.sortPossibleItemsByValuePerWeightRatio();
for (let itemIndex = 0; itemIndex < this.possibleItems.length; itemIndex += 1) {
if (this.totalWeight < this.weightLimit) {
const currentItem = this.possibleItems[itemIndex];
// Detect how much of current items we can push to knapsack.
const availableWeight = this.weightLimit - this.totalWeight;
const maxPossibleItemsCount = Math.floor(availableWeight / currentItem.weight);
if (maxPossibleItemsCount > currentItem.itemsInStock) {
// If we have more items in stock then it is allowed to add
// let's add the maximum allowed number of them.
currentItem.quantity = currentItem.itemsInStock;
} else if (maxPossibleItemsCount) {
// In case if we don't have specified number of items in stock
// let's add only items we have in stock.
currentItem.quantity = maxPossibleItemsCount;
}
this.selectedItems.push(currentItem);
}
}
}
get totalValue() {
/** @var {KnapsackItem} item */
return this.selectedItems.reduce((accumulator, item) => {
return accumulator + item.totalValue;
}, 0);
}
get totalWeight() {
/** @var {KnapsackItem} item */
return this.selectedItems.reduce((accumulator, item) => {
return accumulator + item.totalWeight;
}, 0);
}
}