About: Pseudopolynomial time number partitioning

An Entity of Type: Thing, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In computer science, pseudopolynomial time number partitioning is a pseudopolynomial time algorithm for solving the partition problem. The problem can be solved using dynamic programming when the size of the set and the size of the sum of the integers in the set are not too big to render the storage requirements infeasible. Suppose the input to the algorithm is a multiset of cardinality : S = {x1, ..., xN} Let K be the sum of all elements in S. That is: K = x1 + ... + xN. We will build an algorithm that determines whether there is a subset of S that sums to . If there is a subset, then:

thumbnail
Property Value
dbo:abstract
  • In computer science, pseudopolynomial time number partitioning is a pseudopolynomial time algorithm for solving the partition problem. The problem can be solved using dynamic programming when the size of the set and the size of the sum of the integers in the set are not too big to render the storage requirements infeasible. Suppose the input to the algorithm is a multiset of cardinality : S = {x1, ..., xN} Let K be the sum of all elements in S. That is: K = x1 + ... + xN. We will build an algorithm that determines whether there is a subset of S that sums to . If there is a subset, then: if K is even, the rest of S also sums to if K is odd, then the rest of S sums to . This is as good a solution as possible. e.g.1 S = {1, 2, 3, 5}, K = sum(S) = 11, K/2 = 5, Find a subset from S that is closest to K/2 -> {2, 3} = 5, 11 - 5 * 2 = 1 e.g.2 S = {1, 3, 7}, K = sum(S) = 11, K/2 = 5, Find a subset from S that is closest to K/2 -> {1, 3} = 4, 11 - 4 * 2 = 3 (en)
dbo:thumbnail
dbo:wikiPageID
  • 65877151 (xsd:integer)
dbo:wikiPageLength
  • 5313 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 989571904 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
rdfs:comment
  • In computer science, pseudopolynomial time number partitioning is a pseudopolynomial time algorithm for solving the partition problem. The problem can be solved using dynamic programming when the size of the set and the size of the sum of the integers in the set are not too big to render the storage requirements infeasible. Suppose the input to the algorithm is a multiset of cardinality : S = {x1, ..., xN} Let K be the sum of all elements in S. That is: K = x1 + ... + xN. We will build an algorithm that determines whether there is a subset of S that sums to . If there is a subset, then: (en)
rdfs:label
  • Pseudopolynomial time number partitioning (en)
owl:sameAs
prov:wasDerivedFrom
foaf:depiction
foaf:isPrimaryTopicOf
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License