Content deleted Content added
No edit summary |
→explanation of definition: Corrected spelling errors Tags: Mobile edit Mobile web edit |
||
Line 8:
In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the [[assignment problem]]. When the costs and profits of all agents-task assignment are equal, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the [[Knapsack problem]].
==
In the following, we have ''n'' kinds of items, <math>a_1</math> through <math>a_n</math> and ''m'' kinds of bins <math>b_1</math> through <math>b_m</math>. Each bin <math>b_i</math> is associated with a budget <math>t_i</math>. For a bin <math>b_i</math>, each item <math>a_j</math> has a profit <math>p_{ij}</math> and a weight <math>w_{ij}</math>. A solution is an assignment from items to bins. A feasible solution is a solution in which for each bin <math>b_i</math> the total weight of assigned items is at most <math>t_i</math>. The solution's profit is the sum of profits for each item-bin assignment. The goal is to find a maximum profit feasible solution.
| |||