BINARY KNAPSACK PROBLEM (easy68 simulator- assembly language) Definition The bin
ID: 3707895 • Letter: B
Question
BINARY KNAPSACK PROBLEM (easy68 simulator- assembly language)
Definition
The binary knapsack problem is defined as follows:
Given a set of objects, O = O1, O2, …, On, with weights W = W1, W2, …, Wn and values V = V1, V2, …, Vn, and a
knapsack (bag) with a maximum weight capacity K. The problem is to find the set of objects S with maximum value
without exceeding a weight limit K.
Project
Write and test an Assembly Code for an instance of 16 objects. The code should print the set of objects, total weight
and value of the best configuration.
The code must be able to find the best solution for any set of 16 objects with randomly selected weights and values in
the range 30 to 90, and knapsack weight limits of 400, 500 and 600.
The Assembly Code should use only registers to find the solution, it is not allowed to build any data structures in the
memory (Memory is used only for W, V and K parameters to be read). The code should be compact; 20 to 30
instructions only
Hint: A brute force search is easy to implement with two nested loops in Assembly Language; No AI !
Explanation / Answer
#include<stdio.h>
// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }
// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n+1][W+1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
int main()
{
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val)/sizeof(val[0]);
printf("%d", knapSack(W, wt, val, n));
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.