Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit8c206a9

Browse files
shsinatrekhleb
authored andcommitted
fix unbound knapsack problem with items more than 1(default value) (trekhleb#73)
1 parent6d413d8 commit8c206a9

File tree

2 files changed

+54
-1
lines changed

2 files changed

+54
-1
lines changed

‎src/algorithms/sets/knapsack-problem/Knapsack.js

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -165,7 +165,10 @@ export default class Knapsack {
165165
constavailableWeight=this.weightLimit-this.totalWeight;
166166
constmaxPossibleItemsCount=Math.floor(availableWeight/currentItem.weight);
167167

168-
if(maxPossibleItemsCount){
168+
if(maxPossibleItemsCount>currentItem.itemsInStock){
169+
currentItem.quantity=currentItem.itemsInStock;
170+
this.selectedItems.push(currentItem);
171+
}elseif(maxPossibleItemsCount){
169172
currentItem.quantity=maxPossibleItemsCount;
170173
this.selectedItems.push(currentItem);
171174
}

‎src/algorithms/sets/knapsack-problem/__test__/Knapsack.test.js

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -96,6 +96,31 @@ describe('Knapsack', () => {
9696
newKnapsackItem({value:20,weight:2}),// v/w ratio is 10
9797
];
9898

99+
constmaxKnapsackWeight=15;
100+
101+
constknapsack=newKnapsack(possibleKnapsackItems,maxKnapsackWeight);
102+
103+
knapsack.solveUnboundedKnapsackProblem();
104+
105+
expect(knapsack.totalValue).toBe(84+20+12+10+5);
106+
expect(knapsack.totalWeight).toBe(15);
107+
expect(knapsack.selectedItems.length).toBe(5);
108+
expect(knapsack.selectedItems[0].toString()).toBe('v84 w7 x 1');
109+
expect(knapsack.selectedItems[1].toString()).toBe('v20 w2 x 1');
110+
expect(knapsack.selectedItems[2].toString()).toBe('v10 w1 x 1');
111+
expect(knapsack.selectedItems[3].toString()).toBe('v12 w3 x 1');
112+
expect(knapsack.selectedItems[4].toString()).toBe('v5 w2 x 1');
113+
});
114+
115+
it('should solve unbound knapsack problem with items in stock',()=>{
116+
constpossibleKnapsackItems=[
117+
newKnapsackItem({value:84,weight:7,itemsInStock:3}),// v/w ratio is 12
118+
newKnapsackItem({value:5,weight:2,itemsInStock:2}),// v/w ratio is 2.5
119+
newKnapsackItem({value:12,weight:3,itemsInStock:1}),// v/w ratio is 4
120+
newKnapsackItem({value:10,weight:1,itemsInStock:6}),// v/w ratio is 10
121+
newKnapsackItem({value:20,weight:2,itemsInStock:8}),// v/w ratio is 10
122+
];
123+
99124
constmaxKnapsackWeight=17;
100125

101126
constknapsack=newKnapsack(possibleKnapsackItems,maxKnapsackWeight);
@@ -109,4 +134,29 @@ describe('Knapsack', () => {
109134
expect(knapsack.selectedItems[1].toString()).toBe('v20 w2 x 1');
110135
expect(knapsack.selectedItems[2].toString()).toBe('v10 w1 x 1');
111136
});
137+
138+
it('should solve unbound knapsack problem with items in stock and max weight more than sum of all items',()=>{
139+
constpossibleKnapsackItems=[
140+
newKnapsackItem({value:84,weight:7,itemsInStock:3}),// v/w ratio is 12
141+
newKnapsackItem({value:5,weight:2,itemsInStock:2}),// v/w ratio is 2.5
142+
newKnapsackItem({value:12,weight:3,itemsInStock:1}),// v/w ratio is 4
143+
newKnapsackItem({value:10,weight:1,itemsInStock:6}),// v/w ratio is 10
144+
newKnapsackItem({value:20,weight:2,itemsInStock:8}),// v/w ratio is 10
145+
];
146+
147+
constmaxKnapsackWeight=60;
148+
149+
constknapsack=newKnapsack(possibleKnapsackItems,maxKnapsackWeight);
150+
151+
knapsack.solveUnboundedKnapsackProblem();
152+
153+
expect(knapsack.totalValue).toBe((3*84)+(2*5)+(1*12)+(6*10)+(8*20));
154+
expect(knapsack.totalWeight).toBe((3*7)+(2*2)+(1*3)+(6*1)+(8*2));
155+
expect(knapsack.selectedItems.length).toBe(5);
156+
expect(knapsack.selectedItems[0].toString()).toBe('v84 w7 x 3');
157+
expect(knapsack.selectedItems[1].toString()).toBe('v20 w2 x 8');
158+
expect(knapsack.selectedItems[2].toString()).toBe('v10 w1 x 6');
159+
expect(knapsack.selectedItems[3].toString()).toBe('v12 w3 x 1');
160+
expect(knapsack.selectedItems[4].toString()).toBe('v5 w2 x 2');
161+
});
112162
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp