What is your request?
write three pascal programs that solve the knapsack problem in three different ways
Please wait for the response, this can take some time:
//Solution 1: Dynamic Programming
program Knapsack;
const
MAXWEIGHT = 100;
MAXITEMS = 10;
type
Item = record
weight, value : integer;
end;
var
items : array[1..MAXITEMS] of Item;
maxval : array[0..MAXWEIGHT] of integer;
numitems, weight : integer;
i, w : integer;
begin
// Read data
writeln('How many items?');
readln(numitems);
for i := 1 to numitems do
begin
writeln('Enter weight and value of item ', i);
readln(items[i].weight, items[i].value);
end;
writeln('Maximum weight?');
readln(weight);
// Initialize maxval array
maxval[0] := 0;
for w := 1 to weight do
maxval[w] := -1;
// Calculate maximum value
for i := 1 to numitems do
for w := weight downto 0 do
if (items[i].weight <= w) and (maxval[w - items[i].weight] >= 0) then
if maxval[w] < 0 then
maxval[w] := maxval[w - items[i].weight] + items[i].value
else
maxval[w] := maxval[w] + maxval[w - items[i].weight] + items[i].value;
// Show result
writeln('Maximum value = ', maxval[weight]);
end.
//Solution 2: Greedy Algorithm
program Knapsack;
const
MAXWEIGHT = 100;
MAXITEMS = 10;
type
Item = record
weight, value : integer;
ratio : real;
end;
var
items : array[1..MAXITEMS] of Item;
maxval : array[0..MAXWEIGHT] of integer;
numitems, weight : integer;
i, w : integer;
function cmp(i1, i2 : integer) : boolean;
begin
cmp := items[i1].ratio > items[i2].ratio;
end;
begin
// Read data
writeln('How many items?');
readln(numitems);
for i := 1 to numitems do
begin
writeln('Enter weight and value of item ', i);
readln(items[i].weight, items[i].value);
items[i].ratio := items[i].value / items[i].weight;
end;
writeln('Maximum weight?');
readln(weight);
// Sort items by ratio
for i := 1 to numitems - 1 do
for j := i + 1 to numitems do
if cmp(j, i) then
begin
items[0] := items[i];
items[i] := items[j];
items[j] := items[0];
end;
// Calculate maximum value
maxval[0] := 0;
for i := 1 to numitems do
for w := weight downto 0 do
if (items[i].weight <= w) and (maxval[w - items[i].weight] >= 0) then
maxval[w] := maxval[w] + items[i].value;
// Show result
writeln('Maximum value = ', maxval[weight]);
end.
//Solution 3: Branch and Bound
program Knapsack;
const
MAXWEIGHT = 100;
MAXITEMS = 10;
type
Item = record
weight, value : integer;
ratio : real;
end;
var
items : array[1..MAXITEMS] of Item;
maxval : array[0..MAXWEIGHT] of integer;
numitems, weight : integer;
i, w : integer;
function cmp(i1, i2 : integer) : boolean;
begin
cmp := items[i1].ratio > items[i2].ratio;
end;
procedure branch_and_bound(i, w : integer; curval : integer);
begin
if i > numitems then
begin
if curval > maxval[w] then
maxval[w] := curval;
exit;
end;
if (items[i].weight <= w) and (curval + maxval[w - items[i].weight] > maxval[w]) then
begin
branch_and_bound(i + 1, w, curval);
branch_and_bound(i + 1, w - items[i].weight, curval + items[i].value);
end;
end;
begin
// Read data
writeln('How many items?');
readln(numitems);
for i := 1 to numitems do
begin
writeln('Enter weight and value of item ', i);
readln(items[i].weight, items[i].value);
items[i].ratio := items[i].value / items[i].weight;
end;
writeln('Maximum weight?');
readln(weight);
// Sort items by ratio
for i := 1 to numitems - 1 do
for j := i + 1 to numitems do
if cmp(j, i) then
begin
items[0] := items[i];
items[i] := items[j];
items[j] := items[0];
end;
// Initialize maxval array
maxval[0] := 0;
for w := 1 to weight do
maxval[w] := -1;
// Calculate maximum value
branch_and_bound(1, weight, 0);
// Show result
writeln('Maximum value = ', maxval[weight]);
end.