It is currently Thu Mar 28, 2024 3:24 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 6 posts ] 
Author Message
Offline
 Post subject: dynamic programming: noob question
Post #1 Posted: Fri Jun 09, 2017 11:18 am 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
I'm trying to get the hang of dynamic programming, and was reading the tutorial here:
https://www.topcoder.com/community/data ... -advanced/

For the first beginner exercise, I tried to just think of the problem at first, before reading ahead, and think of how I might solve the problem. I found that my approach was not the same as what's described, and I was hoping to get advice for how to recognize the benefits of constructing a solution "bottom-up" vs. "top-down".

Specifically, the first question is a DP problem such that, given a list of N coins with values (V1, V2, ..., Vn) and a total sum S, find the minimum number of coins that can be used to get a sum of S.

I stopped here, and thought about how I'd try to solve the problem.

Taking their example of values (1, 3, 5) and S=11, my general approach would be as follows:
1.) See if there are any values V that are less than 11. If not, return -1.
2.) Check a hash table (for storing intermediate results) to see if I already have minimum sums for S=10, S=8, or S=6. If the hash table has no values, recursively get the minimum number of coins required for sum (11-1=10), (11-3=8), and (11-5=6), and store the results in the hash table. If the return value of any of these were unsatisfiable (i.e. -1), omit from the set.
3.) Get the minimum of the values returned from the recursive calls, and add 1. That's my minimum for the current sum S=11.

Obviously, this is different from the approach given in the article. Intuitively, I try to approach the problem "top-down". I try to start at the top sum S=11, simulate using that coin, and get the result for S-Vi for each value Vi.

The article, rather, describes a "bottom-up" approach of using states: first identify state S=0, then build on that to create state S=1, all the way up to the state for the final solution.

I have two questions:
1.) Is my approach infeasible? What are the benefits of starting "bottom-up" rather than from the "top-down"?
2.) Intuitively, I see the problem as one that requires a "top-down" approach. What aspects of a problem can I look for that would suggest a "bottom-up" approach is better?

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject: Re: dynamic programming: noob question
Post #2 Posted: Fri Jun 09, 2017 11:36 am 
Gosei

Posts: 1590
Liked others: 886
Was liked: 527
Rank: AGA 3k Fox 3d
GD Posts: 61
KGS: dfan
Your approach is fine. It also avoids computing information that you don't need (you solve only the subproblems relevant to your actual problem). When I used DP for a couple of problems in the first L19 programming contest, I used your top-down approach.

Which approach I would use on any given problem varies. If I know that I'm going to need to solve every subproblem anyway, I might go bottom-up and not worry about memoization and recursion. If I knew that only a very small number of subproblems were relevant to any given top-level problem, I would definitely go top-down. For example, I would never go bottom-up on the peg-jumping problem from the first week.

Top
 Profile  
 
Offline
 Post subject: Re: dynamic programming: noob question
Post #3 Posted: Fri Jun 09, 2017 11:55 am 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
I'd highly recommend getting "Competitive Programming 3" by Steven and Felix Halim for answers to these kinds of questions :D. Here is what they wrote regarding top-down vs bottom-up approaches to DP (screenshot is taken from the first edition, which is available for free on their site so it should be legal):

Image

Top
 Profile  
 
Offline
 Post subject: Re: dynamic programming: noob question
Post #4 Posted: Fri Jun 09, 2017 1:29 pm 
Honinbo

Posts: 9545
Liked others: 1600
Was liked: 1711
KGS: Kirby
Tygem: 커비라고해
Thanks. It's a relief to know that my method might still work. I think it's a good point to watch out for stack overflows with top down approach.

_________________
be immersed

Top
 Profile  
 
Offline
 Post subject:
Post #5 Posted: Fri Jun 09, 2017 3:24 pm 
Honinbo
User avatar

Posts: 8859
Location: Santa Barbara, CA
Liked others: 349
Was liked: 2076
GD Posts: 312
Solomon wrote:
Competitive Programming 3
Off off-topic:
Fascinating. I was curious if competitive cooking books existed ( in addition to competitive cooking shows ); a quick search on Amazon seems to return only the TV shows. :)

Top
 Profile  
 
Offline
 Post subject: Re: dynamic programming: noob question
Post #6 Posted: Fri Jun 09, 2017 4:52 pm 
Gosei
User avatar

Posts: 1435
Location: California
Liked others: 53
Was liked: 171
Rank: Out of practice
GD Posts: 1104
KGS: fwiffo
My top-down solution.
Code:
import functools

@functools.lru_cache(maxsize=None)
def min_coins(target_sum, coins):
    if target_sum == 0:
        return 0
    if target_sum < 0:
        return float('inf')
    return 1 + min(min_coins(target_sum-c, coins) for c in coins)

# min_coins(11, (1, 3, 5)) == 3
# min_coins(5, (2, 4)) == inf -- not possible

_________________
KGS 4 kyu - Game Archive - Keyboard Otaku

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group