# Tag Info

### Ordered open-end knapsack problem optimised for minimum weight range

This can be solved with dynamic programming. Let $W[1,\dots,n]$ denote the weights of the items. Fix a value of $\ell$. Define the array $A[\cdot,\cdot]$ as $A[i,j] =$ the smallest value of $h$ ...
• 149k
Accepted

### Algorithm for a modified worker-task assignment problem with groups of tasks and substitutability between tasks within groups

You can solve this problem as follows. Build a bipartite graph with one vertex per worker and one vertex per group of tasks (one vertex for the entire group; not one vertex per task). The cost of ...
• 149k
1 vote

### What data structure/s can I use for fastest lookup of a permutation between two arrays of pairs (preserving order)?

If I understand correctly, we can reformulate your problem as following: We have a database that contains a set of sets $S_1,\dots,S_n$. You are given an input set $I$. The goal is to determine ...
• 149k

### For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Imagine in real life an area full of mountains. Every village has a short connection to a central point X, but all other connections between villages are very, very long, due to the mountains. The ...
• 26.8k
This problem is strongly NP-hard. A set of transactions can be regarded as a directed graph. Let $A$ be the set of vertices corresponding to players with positive losses and let $B$ be the set of ...