Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

Knapsack problem

Index Knapsack problem

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. [1]

49 relations: Accelerando, Applied mathematics, Approximation algorithm, Baby-step giant-step, Backpack, Big O notation, Bin packing problem, Change-making problem, Combinatorial auction, Combinatorial optimization, Combinatorics, Computational complexity theory, Computer science, Computers and Intractability, Continuous knapsack problem, Cryptography, Cryptonomicon, Cutting stock problem, Daily fantasy sports, David S. Johnson, Decision problem, Dungeons & Dragons, Dynamic programming, Fixed-point arithmetic, George Dantzig, Greatest common divisor, Greedy algorithm, Hybrid algorithm, Investment, Karp's 21 NP-complete problems, Knapsack cryptosystems, List of knapsack problems, Meet-in-the-middle attack, Merkle–Hellman knapsack cryptosystem, NP-completeness, NP-hardness, Packing problems, Polynomial-time approximation scheme, Portfolio (finance), Pseudo-polynomial time, Public-key cryptography, Quadratic knapsack problem, Resource allocation, Rosetta Code, Securitization, Subset sum problem, Suffix tree, The Elder Scrolls, Tobias Dantzig.


Accelerando is a 2005 science fiction novel consisting of a series of interconnected short stories written by British author Charles Stross.

New!!: Knapsack problem and Accelerando · See more »

Applied mathematics

Applied mathematics is the application of mathematical methods by different fields such as science, engineering, business, computer science, and industry.

New!!: Knapsack problem and Applied mathematics · See more »

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to NP-hard optimization problems with provable guarantees on the distance of the returned solution to the optimal one.

New!!: Knapsack problem and Approximation algorithm · See more »

Baby-step giant-step

In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm for computing the discrete logarithm.

New!!: Knapsack problem and Baby-step giant-step · See more »


A backpack — also called bookbag, kitbag, knapsack, rucksack, rucksac, pack, sackpack or backsack — is, in its simplest form, a cloth sack carried on one's back and secured with two straps that go over the shoulders, but there can be variations to this basic design.

New!!: Knapsack problem and Backpack · See more »

Big O notation

Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.

New!!: Knapsack problem and Big O notation · See more »

Bin packing problem

In the bin packing problem, objects of different volumes must be packed into a finite number of bins or containers each of volume V in a way that minimizes the number of bins used.

New!!: Knapsack problem and Bin packing problem · See more »

Change-making problem

The change-making problem, also known as minimum coin change problem, addresses the question of finding the minimum number of coins (of certain denominations) that add up to a given amount of money refer.

New!!: Knapsack problem and Change-making problem · See more »

Combinatorial auction

A combinatorial auction is a type of smart market in which participants can place bids on combinations of discrete items, or “packages”, rather than individual items or continuous quantities.

New!!: Knapsack problem and Combinatorial auction · See more »

Combinatorial optimization

In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects.

New!!: Knapsack problem and Combinatorial optimization · See more »


Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures.

New!!: Knapsack problem and Combinatorics · See more »

Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: Knapsack problem and Computational complexity theory · See more »

Computer science

Computer science deals with the theoretical foundations of information and computation, together with practical techniques for the implementation and application of these foundations.

New!!: Knapsack problem and Computer science · See more »

Computers and Intractability

In computer science, more specifically computational complexity theory, Computers and Intractability: A Guide to the Theory of NP-Completeness is an influential textbook by Michael Garey and David S. Johnson.

New!!: Knapsack problem and Computers and Intractability · See more »

Continuous knapsack problem

In theoretical computer science, the continuous knapsack problem (also known as the fractional knapsack problem) is an algorithmic problem in combinatorial optimization in which the goal is to fill a container (the "knapsack") with fractional amounts of different materials chosen to maximize the value of the selected materials.

New!!: Knapsack problem and Continuous knapsack problem · See more »


Cryptography or cryptology (from κρυπτός|translit.

New!!: Knapsack problem and Cryptography · See more »


Cryptonomicon is a 1999 novel by American author Neal Stephenson, set in two different time periods.

New!!: Knapsack problem and Cryptonomicon · See more »

Cutting stock problem

In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted.

New!!: Knapsack problem and Cutting stock problem · See more »

Daily fantasy sports

Daily fantasy sports (DFS) are a subset of fantasy sport games.

New!!: Knapsack problem and Daily fantasy sports · See more »

David S. Johnson

David Stifler Johnson (December 9, 1945 – March 8, 2016) was an American computer scientist specializing in algorithms and optimization.

New!!: Knapsack problem and David S. Johnson · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: Knapsack problem and Decision problem · See more »

Dungeons & Dragons

Dungeons & Dragons (abbreviated as D&DMead, Malcomson; ''Dungeons & Dragons'' FAQ or DnD) is a fantasy tabletop role-playing game (RPG) originally designed by Gary Gygax and Dave Arneson.

New!!: Knapsack problem and Dungeons & Dragons · See more »

Dynamic programming

Dynamic programming is both a mathematical optimization method and a computer programming method.

New!!: Knapsack problem and Dynamic programming · See more »

Fixed-point arithmetic

In computing, a fixed-point number representation is a real data type for a number that has a fixed number of digits after (and sometimes also before) the radix point (after the decimal point '.' in English decimal notation).

New!!: Knapsack problem and Fixed-point arithmetic · See more »

George Dantzig

George Bernard Dantzig (November 8, 1914 – May 13, 2005) was an American mathematical scientist who made important contributions to operations research, computer science, economics, and statistics.

New!!: Knapsack problem and George Dantzig · See more »

Greatest common divisor

In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers.

New!!: Knapsack problem and Greatest common divisor · See more »

Greedy algorithm

A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum.

New!!: Knapsack problem and Greedy algorithm · See more »

Hybrid algorithm

A hybrid algorithm is an algorithm that combines two or more other algorithms that solve the same problem, either choosing one (depending on the data), or switching between them over the course of the algorithm.

New!!: Knapsack problem and Hybrid algorithm · See more »


In general, to invest is to allocate money (or sometimes another resource, such as time) in the expectation of some benefit in the future – for example, investment in durable goods, in real estate by the service industry, in factories for manufacturing, in product development, and in research and development.

New!!: Knapsack problem and Investment · See more »

Karp's 21 NP-complete problems

In computational complexity theory, Karp's 21 NP-complete problems are a set of computational problems which are NP-complete.

New!!: Knapsack problem and Karp's 21 NP-complete problems · See more »

Knapsack cryptosystems

Knapsack Cryptosystems are cryptosystems which security is based on the hardness of solving the knapsack problem.

New!!: Knapsack problem and Knapsack cryptosystems · See more »

List of knapsack problems

The knapsack problem is one of the most studied problems in combinatorial optimization, with many real-life applications.

New!!: Knapsack problem and List of knapsack problems · See more »

Meet-in-the-middle attack

The meet-in-the-middle attack (MITM) is a generic space–time tradeoff cryptographic attack against encryption schemes which rely on performing multiple encryption operations in sequence.

New!!: Knapsack problem and Meet-in-the-middle attack · See more »

Merkle–Hellman knapsack cryptosystem

The Merkle–Hellman knapsack cryptosystem was one of the earliest public key cryptosystems invented by Ralph Merkle and Martin Hellman in 1978.

New!!: Knapsack problem and Merkle–Hellman knapsack cryptosystem · See more »


In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

New!!: Knapsack problem and NP-completeness · See more »


NP-hardness (''n''on-deterministic ''p''olynomial-time hardness), in computational complexity theory, is the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP".

New!!: Knapsack problem and NP-hardness · See more »

Packing problems

Packing problems are a class of optimization problems in mathematics that involve attempting to pack objects together into containers.

New!!: Knapsack problem and Packing problems · See more »

Polynomial-time approximation scheme

In computer science, a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems).

New!!: Knapsack problem and Polynomial-time approximation scheme · See more »

Portfolio (finance)

In finance, a portfolio is a collection of investments held by an investment company, hedge fund, financial institution or individual.

New!!: Knapsack problem and Portfolio (finance) · See more »

Pseudo-polynomial time

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input) — but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.

New!!: Knapsack problem and Pseudo-polynomial time · See more »

Public-key cryptography

Public-key cryptography, or asymmetric cryptography, is any cryptographic system that uses pairs of keys: public keys which may be disseminated widely, and private keys which are known only to the owner.

New!!: Knapsack problem and Public-key cryptography · See more »

Quadratic knapsack problem

The quadratic knapsack problem (QKP), first introduced in 19th century, is an extension of knapsack problem that allows for quadratic terms in the objective function: Given a set of items, each with a weight, a value, and an extra profit that can be earned if two items are selected, determine the number of item to include in a collection without exceeding capacity of the knapsack, so as to maximize the overall profit.

New!!: Knapsack problem and Quadratic knapsack problem · See more »

Resource allocation

In economics, resource allocation is the assignment of available resources to various uses.

New!!: Knapsack problem and Resource allocation · See more »

Rosetta Code

Rosetta Code is a wiki-based programming chrestomathy website with implementations of common algorithms and solutions to various programming problems in many different programming languages.

New!!: Knapsack problem and Rosetta Code · See more »


Securitization is the financial practice of pooling various types of contractual debt such as residential mortgages, commercial mortgages, auto loans or credit card debt obligations (or other non-debt assets which generate receivables) and selling their related cash flows to third party investors as securities, which may be described as bonds, pass-through securities, or collateralized debt obligations (CDOs).

New!!: Knapsack problem and Securitization · See more »

Subset sum problem

In computer science, the subset sum problem is an important problem in complexity theory and cryptography.

New!!: Knapsack problem and Subset sum problem · See more »

Suffix tree

In computer science, a suffix tree (also called PAT tree or, in an earlier form, position tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values.

New!!: Knapsack problem and Suffix tree · See more »

The Elder Scrolls

The Elder Scrolls is a series of action role-playing open world fantasy video games primarily developed by Bethesda Game Studios and published by Bethesda Softworks.

New!!: Knapsack problem and The Elder Scrolls · See more »

Tobias Dantzig

Tobias Dantzig (February 19, 1884 – August 9, 1956) was a mathematician of Baltic German and Russian American heritage, the father of George Dantzig, and the author of Number: The Language of Science (A critical survey written for the cultured non-mathematician) (1930) and Aspects of Science (New York, Macmillan, 1937).

New!!: Knapsack problem and Tobias Dantzig · See more »

Redirects here:

0-1 Knapsack problem, 0-1 knapsack problem, 0/1 knapsack problem, Algorithms for solving knapsack problems, BKP, Backpack problem, Binary knapsack problem, Integer knapsack problem, Knapsack Problem, Napsack problem, Unbounded Knapsack Problem, Unbounded knapsack problem.


[1] https://en.wikipedia.org/wiki/Knapsack_problem

Hey! We are on Facebook now! »