Package org.drip.sample.subarray

Class PseudoPolynomialSubsetSum

java.lang.Object
org.drip.sample.subarray.PseudoPolynomialSubsetSum
public class PseudoPolynomialSubsetSum
extends java.lang.Object
PseudoPolynomialSubsetSum illustrates the Dynamic Programming Based Maximum Sequential Sub-array Sum Algorithm. The References are:

  • Bringmann, K. (2017): A near-linear Pseudo-polynomial Time Algorithm for Subset Sums Proceedings of the 28th Annual ACM SIAM Symposium on Discrete Algorithms 1073-1084
  • Horowitz, E., and S. Sahni (1974): Computing Partitions with Applications to the Knapsack Problem Journal of the ACM 21 (2) 277-292
  • Kleinberg, J., and E. Tardos (2022): Algorithm Design 2nd Edition Pearson
  • Koiliaris, K., and C. Xu (2016): A Faster Pseudo-polynomial Time Algorithm for Subset Sum https://arxiv.org/abs/1507.02318 arXiV
  • Wikipedia (2020): Subset Sum Problem https://en.wikipedia.org/wiki/Subset_sum_problem




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    PseudoPolynomialSubsetSum()  

  • Method Summary

    Modifier and Type Method Description
    static void main​(java.lang.String[] argumentArray)
    Entry Point

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • PseudoPolynomialSubsetSum

      public PseudoPolynomialSubsetSum()

  • Method Details

    • main

      public static final void main​(java.lang.String[] argumentArray) throws java.lang.Exception
      Entry Point
      Parameters:
      argumentArray - Command Line Argument Array
      Throws:
      java.lang.Exception - Thrown on Error/Exception Situation