Sign Up

Have an account? Sign In Now

Sign In

Forgot Password?

Don't have account, Sign Up Here

Forgot Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

Have an account? Sign In Now

Sorry, you do not have permission to ask a question, You must login to ask a question.

Forgot Password?

Need An Account, Sign Up Here
Sign InSign Up

SIKSHAPATH

SIKSHAPATH Navigation

  • Home
  • Questions
  • Blog
    • Computer Science(CSE)
    • NPTEL
    • Startup
  • Shop
    • Internshala Answers
Search
Ask A Question

Mobile menu

Close
Ask a Question
  • Home
  • Questions
  • Blog
    • Computer Science(CSE)
    • NPTEL
    • Startup
  • Shop
    • Internshala Answers
Home/Questions/Q 22640
Next
In Process
practice503
  • 0
practice503
Asked: October 23, 20222022-10-23T20:18:27+05:30 2022-10-23T20:18:27+05:30In: Data Structure

Solve using fractional knapsack: M=20, n=4 P= (3, 10, 15, …

  • 0

Solve using fractional knapsack:

M=20, n=4

P= (3, 10, 15, 5)

W= (5, 13, 12, 8).

assignmentdaa
  • 1 1 Answer
  • 20 Views
  • 0 Followers
  • 0
Answer
Share
  • Facebook

    1 Answer

    • Voted
    • Oldest
    • Recent
    1. 58n25709
      2023-01-30T10:13:59+05:30Added an answer on January 30, 2023 at 10:13 am

      The fractional knapsack problem involves selecting items to fill a knapsack of limited capacity (M=20 in this case) in such a way as to maximize the total value.

      Here’s how to solve it:

      1. Sort the items in decreasing order of their value per unit weight (i.e. Pi/Wi).
        • Item 1: 3/5 = 0.6
        • Item 2: 10/13 = 0.769
        • Item 3: 15/12 = 1.25
        • Item 4: 5/8 = 0.625
      2. Take the items in the order of the sorted list until the knapsack is full. If a complete item cannot fit, take a fraction of it.
        • Item 3 (15/12) can fit completely, so add it to the knapsack and reduce the capacity to 20-12=8.
        • Item 2 (10/13) can fit completely, so add it to the knapsack and reduce the capacity to 8-13= -5.
        • Item 1 (3/5) cannot fit completely, so add 3/5 of it to the knapsack and reduce the capacity to 0.
        • Item 4 (5/8) is not considered since the knapsack is full.
      3. The total value of the items in the knapsack is 15 + 10 + (3/5)*3 = 22.

      So the optimal solution is to choose items 3, 2 and a fraction of item 1, with a total value of 22.

      • 0
      • Reply
      • Share
        Share
        • Share on WhatsApp
        • Share onFacebook
        • Share on Twitter
        • Share on LinkedIn

    Leave an answer
    Cancel reply

    You must login to add an answer.

    Forgot Password?

    Need An Account, Sign Up Here

    Sidebar

    store ads

    Stats

    • Questions 1k
    • Answers 1k
    • Posts 141
    • Best Answers 64
    • AI 101: Create Presentation Slide Using AI | Gamma App
    • What is the Difference Between Section, Article and Aside in HTML5?
    • How to enable or disable ChatGPT on the Windows 11 taskbar
    • NPTEL Data Mining Assignment Answers 2023 -Week 8
    • NPTEL Data Mining Assignment Answers 2023 -Week 7

    Explore

    • Recent Questions
    • Questions For You
    • Answers With Time
    • Most Visited
    • New Questions
    • Recent Questions With Time

    Footer

    Sikshapath Logo

    Helpful Links

    • Contact
    • Disclaimer
    • Privacy Policy Notice
    • TERMS OF USE
    • FAQs
    • Refund/Cancellation Policy
    • Delivery Policy for Sikshapath

    Follow Us

    © 2021-23 Sikshapath. All Rights Reserved

    Ads Blocker Image Powered by Code Help Pro

    Ads Blocker Detected!!!

    We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

    Refresh
    Powered By
    100% Free SEO Tools - Tool Kits PRO

    Insert/edit link

    Enter the destination URL

    Or link to existing content

      No search term specified. Showing recent items. Search or use up and down arrow keys to select an item.