1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
likoan [24]
3 years ago
15

Andy is trying to put together a holiday gift knapsack (with W=8) for Sarah. He has n items to choose from, each with infinitely

many copies (aka. knapsack with repetitions). Item i has weight wi, and value vi. Andy wants to pick some items (possibility with duplicates) so their total weight is exactly W, while minimizing the total value of the items picked. If OPT(w) denotes the minimum total value needed to make a weight of w, for every 0 ≤ w ≤ W, (i) write the recursive formula for finding OPT(w) and (ii) compute the values of OPT(1) . . . OPT(8) for the following three items: (w1 = 1, v1 = 3), (w2 = 3, v2 = 2), (w3 = 4, v3 = 3).
Computers and Technology
1 answer:
Sever21 [200]3 years ago
3 0

Answer:

See explaination

Explanation:

Given 3 items: {w1 = 1, v1 = 3}, {w2 = 3, v2 = 2}, {w3 = 4, v3 = 3}

Hence OPT(1) = 3, OPT(3) = 2, OPT(4) = 3

Recursive formula for OPT(k) to minimize value is

OPT(k) = INFINITE if k <= 0

= min(3 + OPT(k-1), 2 + OPT(k-3), 3 + OPT(k-4))

Let us calculate OPT(1) to OPT(8)

OPT(1) = 3

OPT(2) = min ( 3 + OPT(1), 2 + OPT(-1), 3 + OPT(-2)) = 6

OPT(3) = 2

OPT(4) = 3

OPT(5) = min ( 3 + OPT(4), 2 + OPT(2), 3 + OPT(1)) = min(6, 8, 6) = 6

OPT(6) = min ( 3 + OPT(5), 2 + OPT(3), 3 + OPT(2)) = min(9, 4, 9) = 4

OPT(7) = min ( 3 + OPT(6), 2 + OPT(4), 3 + OPT(3)) = min(7, 5, 5) = 5

OPT(8) = min ( 3 + OPT(7), 2 + OPT(5), 3 + OPT(4)) = min(8, 8, 6) = 6

You might be interested in
Microsoft recommends when that you create passwords with upper and lowercase letters, numbers, symbols, and use at least _______
harkovskaia [24]

Answer: 8 characters

Explanation:

4 0
2 years ago
PLEASE HELP ITS DRIVERS ED
sasho [114]
I will have to say the answer is.d
3 0
3 years ago
Read 2 more answers
Digital communication and production chapter 17
lisov135 [29]

Answer:

what do i have to do what is the question i have to answer

Explanation:

5 0
2 years ago
How would you use keywords and Boolean operators to help you with a web search?
Over [174]

Answer:

keywords are important for searching for the exact term you are looking for by using the most specific word possible, and boolean operators can help you expand or restrict your search, such as searching for "people named bob AND people named george"

3 0
2 years ago
Which command would you use to swap the words hither and yon on any line with any number of words between them? (You need not wo
REY [17]

Answer:

The command i will use in carrying out such function is

Explanation;

Kindly check the attached file for the command as it can not be written fully in the answer box.

3 0
3 years ago
Other questions:
  • Attacker player X is standing still on a corner kick, as the ball is played, he jumps up with his arms flailing above his should
    8·1 answer
  • ​You work at a call center of a large bank where you answer credit card services related questions from customers. Lately, you h
    14·1 answer
  • Mr. Olgesandravich is proctoring students working at their own pace in an online class. He is generating a spreadsheet that show
    15·1 answer
  • Drive-by hacking is a computer attack where an attacker accesses a wireless computer network, intercepts data, uses network serv
    5·1 answer
  • Which of the following takes place during the research phase
    7·1 answer
  • What does it mean when a computer can't break the rules
    10·2 answers
  • In a ______topology, every device has exactly two neighbors for communication purposes. A failure in any cable or device can tak
    15·2 answers
  • NEED ANS ASAP THANK YOU
    14·1 answer
  • What are some qualities of a good game critic? What are some qualities of a bad game critic?
    7·1 answer
  • You find a picture of a famous department store online that would be great to include in a project of yours. What should you do
    7·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!