Solved

# Knapsack Problem

Posted on 2009-04-04
657 Views
I am uncertain how to solve the following problem and would like some guidance in doing so. Any help is greatly appreciated. Thank you in advance!

Find a subset of the 12 experiments with a total weight of 700 kilograms and a total rating of 49.

Below is a list of the rating and weights, respectively:

9 / 264
8 / 65
8 / 104
8 / 203
7 / 80
6 / 7
6 / 170
6 / 188
5 / 36
4 / 22
3 / 25
2 / 92
0
Question by:ssharp77
• 3
• 2

LVL 4

Accepted Solution

blissbear earned 450 total points
ID: 24070100
Well, I would start by realizing the exclusion subset is smaller in total. If you add up all the weights, you will find they total 72, which means you need to exclude items which would total 23 kg.  The total rating for the entire set is 1256, so you need to exclude 556.

Can you determine a subset that meets these totals?
0

LVL 4

Assisted Solution

blissbear earned 450 total points
ID: 24070106
Also, the total weight is 700 kg, so you can start finding subsets that total to a factor of 10, since those subsets have to add up to be divisible by 10.
0

LVL 4

Expert Comment

ID: 24070109
Otherwise, here are your fomulae: http://en.wikipedia.org/wiki/Knapsack_problem :)
0

LVL 31

Assisted Solution

GwynforWeb earned 50 total points
ID: 24071899
This is not a knapsack problem, although it is similar. The knapsack problem would read,

"Find a subset of the 12 experiments with a total weight of not exceeding 700 kilograms that maximizes the total rating."

I am guessing that a dynamic programming approach could be used for this as well.
0

Author Closing Comment

ID: 31566695
Thank you.
0

LVL 31

Expert Comment

ID: 24073096
I would have been interested to know if this problem is to be solved as exactly stated or is in fact just a knapsack problem.   As stated the problem can also be formulated as a dynamic programming problem.
(note: the link refers to the knapsack not this problem although it is a guide to the solution formulation)
0

## Join & Write a Comment Already a member? Login.

### Suggested Solutions

Title # Comments Views Activity
what is the clinical significance of an elevated Bun? 3 52
Linear algebra 3 52
algorithm 15 77
Calculating Probability 18 62
Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! https://www.google.com/about/careers/students/guide-to-technical-development.html How to Know You are Making a Difference at EE In August, 2013, one …
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.
This video demonstrates how to create an example email signature rule for a department in a company using CodeTwo Exchange Rules. The signature will be inserted beneath users' latest emails in conversations and will be displayed in users' Sent Items…

#### 758 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

#### Need Help in Real-Time?

Connect with top rated Experts

19 Experts available now in Live!