The items formula_8 have non-negative profits formula_12, formula_13, and the elements formula_14 have non-negative weights formula_15, formula_16. The total weight of a set of items is given by the total weight of the elements of the union of the corresponding element sets. The objective is to find a subset of the items with total weight not exceeding the knapsack capacity and maximal profit. If there is more than one constraint (for example, both a volume limit and a weight limit, where the volume and weight of each item are not related), we get the multiply-constrained knapsack problem, multidimensional knapsack problem, or "m"-dimensional knapsack problem. (Note, "dimension" here does not refer to the shape of any items.) This has 0-1, bounded, and unbounded variants; the unbounded one is shown below. The 0-1 variant (for any fixed formula_17) was shown to be NP-complete around 1980 and more strongly, has no FPTAS unless P=NP. The bounded and unbounded variants (for any fixed formula_17) also exhibit the same hardness. For any fixed formula_17, these problems do admit a pseudo-polynomial time algorithm (similar to the one for basic knapsack) and a PTAS. If all the profits are 1, we will try to maximize the number of items which would not exceed the knapsack capacity:  If we have a number of containers (of the same size), and we wish to pack all "n" items in as few containers as possible, we get the bin packing problem, which is modelled by having indicator variables formula_20 container "i" is being used:  The cutting stock problem is identical to the bin packing problem, but since practical instances usually have far fewer types of items, another formulation is often used. Item "j" is needed "Bj" times, each "pattern" of items which fit into a single knapsack have a variable, "xi" (there are "m" patterns), and pattern "i" uses item "j" "bij" times:  If, to the multiple choice knapsack problem, we add the constraint that each subset is of size "n" and remove the restriction on total weight, we get the assignment problem, which is also the problem of finding a maximal bipartite matching:  In the Maximum Density Knapsack variant there is an initial weight formula_21,  and we maximize the density of selected of items which do not violate the capacity constraint:   Although less common than those above, several other knapsack-like problems exist, including:   The last three of these are discussed in Kellerer et al's reference work, "Knapsack Problems".