Scribd
Upload
3 views3 pages

Dynamic Programming for 0/1 Knapsack

The document describes the AlgorithmDKnap, which solves the 0/1 Knapsack problem using a pruned dynamic programming approach. It initializes a state list of profit-weight pairs and iteratively generates new states based on the inclusion of items while avoiding dominated states. Finally, it reconstructs the optimal solution through backtracking.

Uploaded by

thanaitpooja09
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views3 pages

Dynamic Programming for 0/1 Knapsack

The document describes the AlgorithmDKnap, which solves the 0/1 Knapsack problem using a pruned dynamic programming approach. It initializes a state list of profit-weight pairs and iteratively generates new states based on the inclusion of items while avoiding dominated states. Finally, it reconstructs the optimal solution through backtracking.

Uploaded by

thanaitpooja09
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

AlgorithmDKnap(p, w, x, n, m)

// pair[] is an array of PWs (profit-weight pairs)

// This algorithm solves the 0/1 Knapsack problem using a pruned dynamic programming approach

b[0] := 1;

pair[1].p := pair[1].w := 0.0; // Initialize first pair as (0, 0)

t := 1; h := 1; // Start and end indices of current state list S₀

b[1] := next := 2; // next points to the next free spot in pair[]

for i := 1 to n-1 do // Generate Sᵢ from Sᵢ₋₁ for item i

k := t; // Start index for merging

u := Largest(pair, w, t, h, i, m); // Find last valid state from Sᵢ₋₁ that can include item i

for j := t to u do // Process each valid state in Sᵢ₋₁

pp := pair[j].p + p[i]; // New profit if item i is included

ww := pair[j].w + w[i]; // New weight if item i is included

// Insert states from Sᵢ₋₁ that are not dominated by this new state

while ((k < h) and (pair[k].w < ww)) do

pair[next].p := pair[k].p;

pair[next].w := pair[k].w;

next := next + 1;

k := k + 1;

// If state with same weight already exists, keep the one with maximum profit

if ((k < h) and (pair[k].w = ww)) then

{
if pp < pair[k].p then

pp := pair[k].p;

k := k + 1;

// Only add this new state if it is not dominated

if pp > pair[next - 1].p then

pair[next].p := pp;

pair[next].w := ww;

next := next + 1;

// Skip all dominated states (lower profit and weight)

while ((k < h) and (pair[k].p < pair[next - 1].p)) do

k := k + 1;

// Merge remaining states from Sᵢ₋₁ that haven't been handled

while (k < h) do

pair[next].p := pair[k].p;

pair[next].w := pair[k].w;

next := next + 1;

k := k + 1;

// Prepare indices for Sᵢ₊₁ (next iteration)

t := h + 1;

h := next;

b[i + 1] := next; // Save the start index for the next state set
}

// Reconstruct the optimal solution by backtracking through pairs

TraceBack(p, w, pair, x, m, n);

You might also like