Package org.drip.graph.subarray

Class PseudoPolynomialDP

java.lang.Object
org.drip.graph.subarray.SubsetSum
org.drip.graph.subarray.PseudoPolynomialDP
public class PseudoPolynomialDP
extends SubsetSum
PseudoPolynomialDP implements the Sub-set Sum Check using a Pseudo-Polynomial Time Dynamic Programming Scheme. 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
    PseudoPolynomialDP​(int[] numberArray, int target)
    PseudoPolynomialDP Constructor

  • Method Summary

    Modifier and Type Method Description
    boolean[] targetSumExistenceArray()
    Generate the Array of Target Sum Existence Flags
    boolean targetSumExists()
    Indicate if the Target Sum Match exists

    Methods inherited from class org.drip.graph.subarray.SubsetSum

    numberArray, target

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • PseudoPolynomialDP

      public PseudoPolynomialDP​(int[] numberArray, int target) throws java.lang.Exception
      PseudoPolynomialDP Constructor
      Parameters:
      numberArray - The Input Number Array
      target - The Sum Target
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • targetSumExistenceArray

      public boolean[] targetSumExistenceArray()
      Generate the Array of Target Sum Existence Flags
      Returns:
      Array of Target Sum Existence Flags

    • targetSumExists

      public boolean targetSumExists()
      Description copied from class: SubsetSum
      Indicate if the Target Sum Match exists
      Specified by:
      targetSumExists in class SubsetSum
      Returns:
      TRUE - The Target Sum Match exists