Which algorithmic approach guarantees finding the minimal possible difference?
easy🔍 Pattern Recognition Q11 of Q15
Dynamic Programming: Knapsack - Last Stone Weight II
You are given a set of stones with positive integer weights. You want to split them into two groups such that the difference between the sum of weights in the two groups is minimized. Which algorithmic approach guarantees finding the minimal possible difference?
AA dynamic programming approach similar to 0/1 knapsack that finds achievable sums up to half the total weight
BA breadth-first search exploring all subsets of stones without pruning
CA greedy algorithm that repeatedly smashes the two heaviest stones until one or none remain
DA divide-and-conquer approach that recursively splits stones into halves and merges results
Step-by-Step Solution
Step 1: Understand the problem as partitioning stones into two subsets with minimal difference
This is a classic subset-sum variation where we want to find a subset with sum as close as possible to half the total.
Step 2: Recognize that 0/1 knapsack DP can find achievable sums up to half total weight
By using DP to track which sums are possible, we can find the closest sum to half, minimizing the difference.
Final Answer:
Option A -> Option A
Quick Check:
Greedy fails on some inputs; DP guarantees minimal difference [OK]
Quick Trick:Minimal difference -> subset sum DP, not greedy [OK]
