<p>This problem is known under the names <em>"precedence constrained knapsack problem"</em> and/or <em>"partially ordered knapsack problem"</em>. Google will lead you to references to many research papers from the last 40 years, as for instance:</p>

<blockquote>
  <p>JOHNSON, D. S., and NIEMI, K. A., On Knapsacks, Partitions, and a New
  Dynamic Programming Technique for Trees, Mathematics of Operations
  Research, Vol. 8, pp. 1–14, 1983.</p>
</blockquote>

CC BY-SA 3.0
2016-12-26T09:23:51.837Z
That helped me, but what about the knapsack problem _without limiting the knapsacks capacity_? The classical one can be solved easily by an greedy algorithm, if the capacity limit is removed, that's a big difference.
user43752
CC BY-SA 3.0
2016-12-26T09:04:52.103Z
2016-12-26T09:04:52.103Z
Gamow
<p>Consider a set of items, weighted with real numbers / costs. You are supposed to select a subset maximizing the sum of the weights of the selected items. But the following contraints must be observed: Every item can be selected only once. Some items have depedencies: If you select item 1, you also have to select item 2 and item 3. Note: Therefore, it's possible to have items with the following property: You <strong>must</strong> select item 1, if you select item 2 or item 3 (imagine a dependency graph) and there is <strong>no limit</strong>: You can select as many items as you want. Last, fragments of items (like 0.7 times item 1) are not allowed.</p>

<p>I ask for an algorithm or some ideas to this problem.</p>

CC BY-SA 3.0
2016-12-26T01:40:47.110Z
Input already can be exponential (like $n^{O (n) }$), so the brute force algorithm is not very bad and without having extra information  (e.g on dependencies), it's not possible to hope for even good approximations.
Saeed
<graph-algorithms>
Bounded 0/1-knapsack with dependency constraints without limit
user43752
# Bounded 0/1-knapsack with dependency constraints without limit

(Asked by: username_0 on 2016-12-25)

Consider a set of items, weighted with real numbers / costs. You are supposed to select a subset maximizing the sum of the weights of the selected items. But the following contraints must be observed: Every item can be selected only once. Some items have depedencies: If you select item 1, you also have to select item 2 and item 3. Note: Therefore, it's possible to have items with the following property: You **must** select item 1, if you select item 2 or item 3 (imagine a dependency graph) and there is **no limit**: You can select as many items as you want. Last, fragments of items (like 0.7 times item 1) are not allowed.

I ask for an algorithm or some ideas to this problem.

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: Input already can be exponential (like $n^{O (n) }$), so the brute force algorithm is not very bad and without having extra information  (e.g on dependencies), it's not possible to hope for even good approximations.  

---

## 1 answers

### Answer by username_2 on 2016-12-26. Score: 2

This problem is known under the names *"precedence constrained knapsack problem"* and/or *"partially ordered knapsack problem"*. Google will lead you to references to many research papers from the last 40 years, as for instance:

> JOHNSON, D. S., and NIEMI, K. A., On Knapsacks, Partitions, and a New
> Dynamic Programming Technique for Trees, Mathematics of Operations
> Research, Vol. 8, pp. 1–14, 1983.

> **Comments:**
> **username_0**: That helped me, but what about the knapsack problem _without limiting the knapsacks capacity_? The classical one can be solved easily by an greedy algorithm, if the capacity limit is removed, that's a big difference.  

---

