Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the proper problem name / algorithm for this problem description in computer science theory?

The problem is that I have X items of varying weighted values that must go into Y containers. The containers are of differing sizes (e.g. hold differing maximum weights). The total load of each container must be approximately equivalent to the others, but the containers don't need to be full or minimized. All of the containers must be used.

This reminds me of the "knapsack" problem, but I have multiple knapsacks of differing sizes and the loads between them all must be relatively equivalent (e.g. one knapsack may only hold 12 pounds, and another knapsack may only hold 8 pounds, but they both need to be filled with the same percentage of total weight they can carry). It also reminds me of the "bin packing" problem, but that doesn't deal with the varying bin sizes or that the bins don't need to be full or minimized, they just need equivalent loads and all of them need to be used.

Can anyone please point me in the right direction as to the name of this problem within data structures and algorithm theory? I'd also be interested in any algorithms or heuristics that may be commonly used to solve a problem like this or info about the possible time complexity.

like image 432
aoeu Avatar asked Dec 11 '10 03:12

aoeu


People also ask

What is an algorithm in computer science?

In Computer Science, an algorithm is a list set of instructions, used to solve problems or perform tasks, based on the understanding of available alternatives.

How many algorithms are there in computer science?

There are seven different types of programming algorithms: Sort algorithms. Search algorithms. Hashing.

What is a problem in computer science?

To summarize: A problem is a function or a mapping of inputs to outputs. An algorithm is a recipe for solving a problem whose steps are concrete and unambiguous. Algorithms must be correct, of finite length, and must terminate for all inputs. A program is an instantiation of an algorithm in a programming language.

What is meant by complexity of problems in relation to computer science?

The complexity of a problem is the infimum of the complexities of the algorithms that may solve the problem, including unknown algorithms. Thus the complexity of a problem is not greater than the complexity of any algorithm that solves the problems.


1 Answers

Sounds like multiple-knapsack to me. From Wikipedia:

If we have n items and m knapsacks with capacities Wi, we get the multiple knapsack problem

EDIT: Sorry, missed the bit about each container needing to be similarly loaded. Still, it smells like multiple-knapsack, albeit with an extra constraint.

like image 172
Cameron Skinner Avatar answered Oct 06 '22 23:10

Cameron Skinner