*Sub Set Sum*and

*Integer Knapsack*are few examples of combinatorial optimization problems with

*pseudo*polynomial running time algorithms. Often we the implementation of these pseudo polynomial dynamic programming algorithms is done using a huge array to hold intermediate sub problems (e.g. $OPT[K][n]$ would indicate a presence of a subset in the first $n$ integer elements ($x_1,x_2\ldots x_n$) which sum to $K$). If $N$ is the bound on the subset value you were looking for then the space complexity would $\Theta(Nn)$ -- which is clearly exponential on the input size which is $O(n\log(N))$ bits. To build robust algorithms -- reduce the dependence on the value of $N$ -- for these pseudo polynomial algorithms, it would be efficient if we could exploit the underlying DAG (Directed Acyclic Graph) nature of any dynamic programming formulation. But that might be a little bit more code to traverse the sub-problems in a topological order. However we can make our life a little easy by using a hash table to keep track of the sub-problems, which might add to the worst case asymptotic runtime by a factor of $O(log(nN))$. On the other hand the average case of sub-problem lookup would be a constant and would run fairly efficiently in practice.

The following code is a quick illustration of using a hash tables to keep track (and also lookup) of sub-problems in pseudo polynomial dynamic programming algorithms. You can read the problem statement here . Notice the obvious generalization of the problem (scheduling with constant number of resources) from the way I have formulated the dynamic program.

// 11/15/2014: vamsik@engr.uconn.edu// #include#include #include #include #include #include using namespace std; typedef std::pair KeyType; struct KeyTypeHasher{ inline size_t operator()(const KeyType& a) const { return (a.first)*1729 + a.second; } }; typedef std::unordered_map SubProbType; typedef typename SubProbType::iterator SubProbItr; bool IsFeasible(const std::vector & A, unsigned int G){ SubProbType sub_problems_even, sub_problems_odd; SubProbItr itr; //init// if(A[0] <= G){ sub_problems_even[KeyType(A[0], 0)] = true; sub_problems_even[KeyType(0, A[0])] = true; } for(size_t i=1; i < A.size(); i++){ SubProbType& curr_problems = (i%2) ? sub_problems_even : sub_problems_odd; SubProbType& next_problems = (i%2) ? sub_problems_odd : sub_problems_even; if(curr_problems.empty()){ return false; } next_problems.clear(); //create new sub-problems in the next level// for(itr = curr_problems.begin(); itr != curr_problems.end(); ++itr){ const KeyType &a = itr->first; if( (a.first + A[i]) <= G){ next_problems[ KeyType((a.first+A[i]), a.second)] = true; } if( (a.second + A[i]) <= G){ next_problems[ KeyType(a.first, (a.second + A[i]))] = true; } } curr_problems.clear(); } return ((A.size())%2) ? !(sub_problems_even.empty()) : !(sub_problems_odd.empty()); } int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ size_t T,N; unsigned int G, a; scanf("%lu", &T); for(size_t i=0; i < T; i++){ std::vector A; scanf("%lu %u",&N, &G); for(size_t i=0; i < N; i++){ scanf("%u", &a); A.push_back(a); } printf("%s\n", IsFeasible(A, G) ? "YES" : "NO"); } return 0; }

## No comments:

Post a Comment