Practice - 5 Tasks
Answer the questions below
1fill in blank
easyComplete the code to select the next best item greedily based on value.
DSA Javascript
function greedySelect(items) {
items.sort((a, b) => b.value - a.value);
let result = [];
for (let i = 0; i < items.length; i++) {
if (canAdd(items[i])) {
result.push(items[i]);
}
}
return result;
}
function canAdd(item) {
return [1];
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Returning false prevents adding any item.
Using conditions that filter out items incorrectly.
✗ Incorrect
The greedy approach tries to add every item if possible. Here, canAdd always returns true to simulate adding all items greedily.
2fill in blank
mediumComplete the code to check if adding an item exceeds capacity.
DSA Javascript
function canAdd(item, currentWeight, capacity) {
return currentWeight [1] capacity - item.weight;
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using '>=' causes wrong logic and rejects valid items.
Using '<=' allows equal weight which may or may not be allowed.
✗ Incorrect
We check if currentWeight is less than capacity minus item weight to ensure adding item won't exceed capacity.
3fill in blank
hardFix the error in the greedy algorithm that fails to consider item weights properly.
DSA Javascript
function greedyKnapsack(items, capacity) {
items.sort((a, b) => b.value / b.weight - a.value / a.weight);
let totalWeight = 0;
let result = [];
for (let i = 0; i < items.length; i++) {
if (totalWeight + items[i].weight [1] capacity) {
result.push(items[i]);
totalWeight += items[i].weight;
}
}
return result;
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using '>=' or '>' causes wrong acceptance of overweight items.
Using '<=' may allow total weight equal to capacity which might be acceptable but can cause off-by-one errors.
✗ Incorrect
We must check if totalWeight plus current item's weight is less than capacity to avoid exceeding it.
4fill in blank
hardFill both blanks to complete the function that checks if greedy fails for this input.
DSA Javascript
function greedyFails(items, capacity) {
items.sort((a, b) => a.weight - b.weight);
let totalValue = 0;
let totalWeight = 0;
for (let i = 0; i < items.length; i++) {
if (totalWeight + items[i].weight [1] capacity) {
totalValue += items[i].value;
totalWeight += items[i].weight;
}
}
return totalValue [2] 60;
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using '>=' in weight check allows overweight items.
Using '<=' in value check reverses logic.
✗ Incorrect
We check if total weight plus item weight is less than capacity to add it, and then check if total value is greater than 60 to detect greedy failure.
5fill in blank
hardFill all three blanks to complete the function that demonstrates greedy success condition.
DSA Javascript
function greedySuccess(items, capacity) {
items.sort((a, b) => b.value / b.weight - a.value / a.weight);
let totalWeight = 0;
let totalValue = 0;
for (let i = 0; i < items.length; i++) {
if (totalWeight + items[i].weight [1] capacity) {
totalWeight += items[i].weight;
totalValue += items[i].value;
}
}
return totalValue [2] 100 && totalWeight [3] capacity;
} Drag options to blanks, or click blank then click option'
Attempts:
3 left
💡 Hint
Common Mistakes
Using '>=' in weight check causes overweight items.
Using '<' in value check reverses success condition.
Using '>' in weight check allows overweight.
✗ Incorrect
We add items only if total weight plus item weight is less than capacity, then check if total value is at least 100 and total weight is at most capacity to confirm greedy success.