Tags: %TAGME{ tpaction="" web="Main" tag="" }% view all tags

368. Largest Divisible Subset

Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.

If there are multiple solutions, return any subset is fine.

Example 1:
```nums: [1,2,3]
Result: [1,2] (of course, [1,3] will also be ok)
```
Example 2:
```nums: [1,2,4,8]
Result: [1,2,4,8]
```

You are to find a dynamic programming solution to this problem, and implement it on Leetcode.

Hints:
1. Can you think of a bottom-up approach? How is the larger problem a made up of sub-problems?
2. Review the solution in class of Weighted Interval Scheduling. Consider the methods and data structures of that.
3. DP usually depends on the ordering of objects. How might ordering here be useful?
4. How is an optimal solution for a given size problem useful in constructing a solution for a larger problem.
5. For a given problem size of n, can you first solve all of the problems for 0<i<=n-1 and keep track of those solutions with some sort of a data structure?
6. If you have solved (and have available) the solutions for all smaller problems, how can you select and use the smaller solutions to create a solution for n?
Turn in:
1. Source code for your solution
2. Samples runs showing the operation with input and outputs.
3. An explaination of how this problem includes the concept of an optimal substructure.
4. A complete runtime asymptotic analysis.
Be prepared to discuss you solutions in class.
Edit | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | More topic actions
Topic revision: r2 - 2016-11-15 - JimSkon

 Home Main Web P View Edit Account
Copyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback