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

Commitfd1965e

Browse files
committed
fix unbound knapsack problem with items more than 1(default value)
1 parentd154015 commitfd1965e

File tree

3 files changed

+55
-2
lines changed

3 files changed

+55
-2
lines changed

‎package-lock.json

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎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