Knapsack Light
Description
You found two items in a treasure chest! The first item weighs weight1
and is worth value1
, and the second item weighs weight2
and is worth value2
. What is the total maximum value of the items you can take with you, assuming that your max weight capacity is maxW
and you can’t come back for the items later?
Note that there are only two items and you can’t bring more than one item of each type, i.e. you can’t take two first items or two second items.
Example
- For
value1 = 10
,weight1 = 5
,value2 = 6
,weight2 = 4
, andmaxW = 8
, the output should beknapsackLight(value1, weight1, value2, weight2, maxW) = 10
.
You can only carry the first item.
- For
value1 = 10
,weight1 = 5
,value2 = 6
,weight2 = 4
, andmaxW = 9
, the output should beknapsackLight(value1, weight1, value2, weight2, maxW) = 16
.
You’re strong enough to take both of the items with you.
- For
value1 = 5
,weight1 = 3
,value2 = 7
,weight2 = 4
, andmaxW = 6
, the output should beknapsackLight(value1, weight1, value2, weight2, maxW) = 7
.
You can’t take both items, but you can take any of them.
Input/Output
-
[execution time limit] 4 seconds (js)
-
[input] integer value1
Guaranteed constraints:
2 \leq value1 \leq 20
. -
[input] integer weight1
Guaranteed constraints:
2 \leq weight1 \leq 10
. -
[input] integer value2
Guaranteed constraints:
2 \leq value2 \leq 20
. -
[input] integer weight2
Guaranteed constraints:
2 \leq weight2 \leq 10
. -
[input] integer maxW
Guaranteed constraints:
1 \leq maxW \leq 20
. -
[output] integer
[JavaScript (ES6)] Syntax Tips
1
2
3
4
5
6
// Prints help message to the console
// Returns a string
function helloWorld(name) {
console.log("This prints to the console when you Run Tests");
return "Hello, " + name;
}
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function knapsackLight(value1, weight1, value2, weight2, maxW) {
var val;
if (value2 > value1) {
val = value1;
value1 = value2;
value2 = val;
val = weight1;
weight1 = weight2;
weight2 = val;
}
val = 0;
if (weight1 <= maxW) {
val += value1;
maxW -= weight1
}
if (weight2 <= maxW)
val += value2;
return val;
}