"Greedy, but Better": Given a knapsack problem with a weight capacity C, and n items, and each item has a weight W[1:n] and monetary value P[1:n]. You have to determine which items to take so that the total weight is C, and the total value (profit) is maximized. In this case we are considering an integer problem, so you can either take an item, or not take an item, you cannot take it fractionally.
If you recall, the greedy algorithm (which orders the items in order of value to weight ratio), does not perform very well. You can make it perform very very poorly. However, a simple fix can make this algorithm only as bad as a ratio of 2 (compared to the best possible solution). Explain how you fix the greedy algorithm.
suject
design and analysis algorithm
The Fractional Knapsack Problem usually sounds like this:
for example: Ted Thief has just broken into the Fort Knox! He sees himself in a room with n piles of gold dust. Because the each pile has a different purity, each pile also has a different value (v[i]) and a different weight (c[i]). Ted has a knapsack that can only hold W kilograms.
Given n, v, c and W, calculate which piles Ted should completely put into his knapsack and which he should put only a fraction of.
So, for this input:
n = 5
c = {12, 1, 2, 1, 4}
v = {4, 2, 2, 1, 10}
W = 15
Ted should take piles 2, 3, 4 and 5 completely and about 58% of pile 1.
You’re usually dealling with a knapsack problem when you’re give the cost and the benefits of certain objects and asked to obtain the maximum benefit so that the sum of the costs is smaller than a given value. You’ve got the fractional knapsack problem when you can take fractions (as opposed to all or nothing) of the objects.
The Algorithm
This is a standard greedy algorithm. In fact, it’s one of the classic examples.
The idea is to calculate for each object the ratio of value/cost, and sort them according to this ratio. Then you take the objects with the highest ratios and add them until you can’t add the next object as whole. Finally add as much as you can of the next object.
So, for our example:
v = {4, 2, 2, 1, 10}
c = {12, 1, 2, 1, 4}
r = {1/3, 2, 1, 1, 5/2}
From this it’s obvious that you should add the objects: 5, 2, 3,
4 and then as much as possible of 1.
The output of my programme is this:
Added object 5 (10$, 4Kg) completly in the bag. Space left:
11.(Total=15)
Added object 2 (2$, 1Kg) completly in the bag. Space left:
10.
Added object 3 (2$, 2Kg) completly in the bag. Space left: 8.
Added object 4 (1$, 1Kg) completly in the bag. Space left: 7.
Added 58% (4$, 12Kg) of object 1 in the bag.
Filled the bag with objects worth 15.48$.
The Programme:
Now, you could implement the algorithm as stated, but for practical reasons you may wish to trade speed for simplicity. That’s what I’ve done here: instead of sorting the objects, I simply go through them every time searching for the best ratio. This modification turns an O(n*lg(n))algorithm into an O(n2) one. For small values of n, this doesn’t matter and n is usually small.
here the code:
#include <stdio.h>
int n = 5; /* The number of objects */
int c[10] = {12, 1, 2, 1, 4}; /* c[i] is the *COST* of the ith object; i.e. what
YOU PAY to take the object */
int v[10] = {4, 2, 2, 1, 10}; /* v[i] is the *VALUE* of the ith object; i.e.
what YOU GET for taking the object */
int W = 15; /* The maximum weight you can take */
void simple_fill() {
int cur_w;
float tot_v;
int i, maxi;
int used[10];
for (i = 0; i < n; ++i)
used[i] = 0; /* I have not used the ith object yet */
cur_w = W;
while (cur_w > 0) { /* while there's still room*/
/* Find the best object */
maxi = -1;
for (i = 0; i < n; ++i)
if ((used[i] == 0) &&
((maxi == -1) || ((float)v[i]/c[i] > (float)v[maxi]/c[maxi])))
maxi = i;
used[maxi] = 1; /* mark the maxi-th object as used */
cur_w -= c[maxi]; /* with the object in the bag, I can carry less */
tot_v += v[maxi];
if (cur_w >= 0)
printf("Added object %d (%d$, %dKg) completly in the bag. Space left: %d.\n", maxi + 1, v[maxi], c[maxi], cur_w);
else {
printf("Added %d%% (%d$, %dKg) of object %d in the bag.\n", (int)((1 + (float)cur_w/c[maxi]) * 100), v[maxi], c[maxi], maxi + 1);
tot_v -= v[maxi];
tot_v += (1 + (float)cur_w/c[maxi]) * v[maxi];
}
}
printf("Filled the bag with objects worth %.2f$.\n", tot_v);
}
int main(int argc, char *argv[]) {
simple_fill();
return 0;
}
"Greedy, but Better": Given a knapsack problem with a weight capacity C, and n items, and...
Recall that in the "Knapsack Problem", there are n items having respective values V1..n) and weights W1..n), all greater than 0 and one needs to maximize the total value of the subset of the items placed in the knapsack limited by a weight capacity of W In the 0-1 Knapsack Problem, each item must be either be included or excluded in its entirety, in light of the fact that this problem is to be "NP-Complete", how can one solve the...
2 Knapsack Problem In a Knapsack problem, given n items {11, I2, -.., In} with weight {wi, w2, -.., wn) and value fvi, v2, ..., vn], the goal is to select a combination of items such that the total value V is maximized and the total weight is less or equal to a given capacity W. Tt i=1 In this question, we will consider two different ways to represent a solution to the Knapsack problem using an array with size...
For given capacity of knapsack W and n items {i1,i2,...,in} with its own value {v1,v2,...,vn} and weight {w1,w2,...,wn}, find a greedy algorithm that solves fractional knapsack problem, and prove its correctness. And, if you naively use the greedy algorithm to solve 0-1 knapsack problem with no repetition, then the greedy algorithm does not ensure an optimal solution anymore. Give an example that a solution from the greedy algorithm is not an optimal solution for 0-1 knapsack problem.
solution is required in pseudo code please. 2 Knapsack Problem În al Knapsack problem. given n items(11-12. . . . . 1"} with weight {w1·W2. . . . . ux) and value (n 2, .., nJ, the goal is to select a combination of items such that the total value V is maximized and the total weight is less or equal to a given capacity In this question, we will consider two different ways to represent a solution to the...
Consider the following greedy algorithm for the knapsack problem: each time we pick the item with the highest value to weight ratio to the bag. Skip items that will make the total weight exceeded the capacity of the bag. Find a counterexample to show that this approach will not work, and the result could be 100 times worse than the optimal solution. That is, construct a table of set of items with weight and values and find a bag capacity...
In weighted knapsack problem, given the knapsack capacity is 16 and the following items (Weight, Value), what is the maximum value we can take away. Explain shortly how and by what approach you arrived at this solution. Item 1 (4, 12) Item 2 (3, 14) Item 3 (7, 22) Item 4 (8, 32) Item 5 (4, 24) Item 6 (6, 20)
5) (10 pts) Greedy Algorithms The 0-1 Knapsack problem is as follows: you are given a list of items, each item has an integer weight and integer value. The goal of the problem is to choose a subset of the items which have a sum of weights less than or equal to a given W with a maximal sum of values. For example, if we had the following five items (each in the form (weight, value)): 11(6, 13), 2(4, 10),...
In a Knapsack problem, given n items {I1, I2, · · · , In} with weight {w1, w2, · · · , wn} and value {v1,v2, ···, vn}, the goal is to select a combination of items such that the total value V is maximized and the total weight is less or equal to a given capacity W . i-1 In this question, we will consider two different ways to represent a solution to the Knapsack problem using . an...
There are n items in a store. For each item i=1,2,...,n the weight of the item is wi and the value of the item is vi. A thief is carrying a knapsack of weight W. In this version of a problem the items can be broken into smaller pieces, so the thief may decide to carry only a fraction xi of object i, where 0≤xi ≤1. Item i contributes xiwi to the total weight in the knapsack, and xivi to...
1. Fractional Knapsack Problem Algorithm Which best describes the tightest range of the number of items with only fractional inclusion (i.e. not entirely included or excluded) in the knapsack? (Let n denote the number of items for possible inclusion.) A) At least 0 items and at most n items B) At least 1 items and at most n items C) Exactly n items D) At least 0 items and at most n-1 items E) At least 1 items and at...