 # Greedy Knapsack 0/1 and Fractional Problem

Subject Computer Science Data Structures and Algorithms

## Question

1. We have 5 objects, and the weights and values are
No.   1   2   3   4   5
w    10 20 30 40 50
v      20 30 66 60 55
The knapsack can carry a weight not exceeding 90, find a subset items and give the total weight and value for following algorithms:
1) By using the algorithm of greedy of value for 0-1 knapsack problem? By selecting the highest value first.
2) By using the algorithm of greedy of weight for 0-1 knapsack problem? By selecting lightest item first.
3) By using the algorithm of greedy of density for 0-1 knapsack problem? By selecting the highest density item first.
4) By using the algorithm of greedy of density for fractional knapsack problem? By selecting the highest density item first.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

In this version of the problem we can either take an object or not (since it is 0-1 Knapsack). We sort the object in the non-increasing order by their values and we take the corresponding object as long as weight does not exceed 90.
This algorithm will take into knapsack: object 3, object 4, and object 2 (we notice it can’t take object 5 after object 4 because the maximum allowed weight would be exceeded).
The achieved weight is 30 + 40 +20 =90.
The achieved value is 66 + 60 + 30 = 156....

This is only a preview of the solution. Please use the purchase button to see the entire solution

## Related Homework Solutions

Kruskal Minimum Spanning Tree Algorithm Run on Example Graph \$35.00
Benchmark
Report
Kruskal
Java
Report
Analysis
Complexity
Test
Case
Data
Problem
Critical
Operation
Comprehensive
Documentation
Approach
Lesson
Learned
Limitation
Expectation
Big-O
Graph
Input
Set
Introduction
Source
File
Code
M
5 Problems Involving Greedy Algorithms \$50.00
Greedy
Algorithm
Analysis
Optimal
Program
Disk
Megabyte
Storage
Capacity
Decimalization
Denomination
Change-making
Half-crown
Florin
Shilling
Sixpence
Threepence
Pence
Coin
Solution
Selection
Sort
Framework
Decomposition
Egyptian
Function Asymptotic Growth & Basic Java Programming Questions \$15.00
Asymptotic
Growth Rate
Java
Main
Maryland
State
Method
Output
Class
Extends
Computer Science
Data Structures
Algorithms
Computer Engineering Questions \$4.00
Computer Science
Engineering
Intel 8086
Systems
DRAM Memory
RAS
Processors
States
Writing
Propagation
Data Paths
Time Requirements
Clocking Rate
Access Time
Floyd-Warshall's Algorithm - Behavioral Analysis \$50.00
Floyd
Warshall
Algorithm
Analysis
Java
Benchmark
Directed
Weighted
Graph
Complexity
Big-O
Documentation
Computer Science
Data Structures
Algorithms
Live Chats