1 Tokens
You’re playtesting a new boardgame from one of your friends in the Game Design major, and they want your help to figure out the optimal strategy. The game has n rounds and in each round 1  i  n you must acquire si tokens. There are two possible ways to acquire tokens in round i:
- A  Spend r dollars per token, so r · si in total, to acquire all token of round i.
- B Â Spend C dollars to acquire the tokens of round i and of the next 3 rounds, independently of how many there are. (If you do this in round i, then your next choices concern rounds i + 4 and greater).
Example. Suppose r = 1, C = 40, and the sequence of si is 11, 9, 9, 12, 12, 12, 12, 9, 9, 11. Then the cheapest way to acquire all the tokens is to choose action A for the first three rounds, then action B once, and then action A for the final three rounds.
Give a dynamic programming algorithm for finding the cheapest way to acquire all tokens, given the sequence s1 , s2 , . . . , sn . You must describe not only how you determine the value of the optimal sequence of actions, but also the sequence of actions itself.
Answers
Status NEW
Posted 28 Apr 2017 07:04 AM
My Price 8.00
-----------
Attachments
file 1493365052-Solutions file 2.docx preview (51 words )
H-----------ell-----------o S-----------ir/-----------Mad-----------am
-----------
Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------.
-----------
Th-----------ank----------- yo-----------u
-----------
Not Rated(0)