I am wondering about an issue that I found here: Finding cheapest combination of items with conditions on the selection I wanted to continue discussing this because I find this very interesting and the solution really cool, but I have issues understanding it completely. So I thought asking this in the comments on the other question might be out of scope.
The question was on how to find the cheapest way to buy an amount n from sellers S that have different prices on item i. For completeness, the table:
Name Price Units in storage
Supplier #1 17$ 1 Unit
Supplier #2 18$ 3 Units
Supplier #3 23$ 5 Units
The suggested solution (and correct answer) was to use Dijkstra's algorithm. I would like to discuss the implications of this and the time complexity. First of, I have created a very simple java-loop to determine different prices on different combinations:
public class Graph2 {
public static class Vendor {
int itemCount = 0;
double price = 0.0;
public Vendor(int itemCount, double price ) {
this.price = price;
this.itemCount = itemCount;
}
}
public static class Combo {
public Combo(int aCount, int bCount, int cCount, double total) {
this.aCount = aCount;
this.bCount = bCount;
this.cCount = cCount;
this.total = total;
}
public int aCount;
public int bCount;
public int cCount;
public double total;
}
public static int counter = 0;
public static void main(String[] args) {
Vendor a = new Vendor(1, 17.0);
Vendor b = new Vendor(3, 18.0);
Vendor c = new Vendor(5, 23.0);
Map<Integer, List<Combo>> comboMap = new HashMap<>();
for(int i_a = 0; i_a <= a.itemCount; i_a++) {
for(int i_b = 0; i_b <= b.itemCount; i_b++) {
for(int i_c = 0; i_c <= c.itemCount; i_c++) {
StringBuffer buf = new StringBuffer();
buf.append("A: ").append(i_a).append(" B: ").append(i_b).append(" C: ").append(i_c);
int totalCount = i_a + i_b + i_c;
List<Combo> combos = comboMap.computeIfAbsent(totalCount, k -> new ArrayList<>());
combos.add(new Combo(i_a, i_b, i_c, i_a * a.price + i_b * b.price + i_c * c.price));
}
}
}
comboMap.entrySet().stream().forEach(e -> {
Integer totalCount = e.getKey();
List<Combo> combos = e.getValue();
combos.forEach( combo -> {
counter++;
StringBuffer buffer = new StringBuffer();
buffer.append("Buying ").append(totalCount).append(" items. ").append("A: ").append(combo.aCount)
.append(" B: ").append(combo.bCount).append(" C: ").append(combo.cCount).append(" Costs: ").append(combo.total);
System.out.println(buffer.toString());
});
});
System.out.println("Combinations: " + counter);
}
}
This yields something like this:
// omitting the first X lines for they are not that important
Buying 8 items. A: 1 B: 3 C: 4 Costs: 163.0
Buying 9 items. A: 1 B: 3 C: 5 Costs: 186.0
Combinations: 48
So, for this specific problem, iterating through all sellers on their amount of items and calculating what any combination of items costs would take 48 iterations. Or: a * b * c, where a,b and c are the respective item counts of the sellers (48 because I count the 0-results as well)
Now, moving to a graph. I understand that this is a shortest-path problem (or can be modelled as such). This means we can have a graph that represents buy-operations, one at a time, then we can use Dijkstra and determine the shortest path by adding the price on each edge to the total weight.
I struggeled to even construct the graph (apart from manually adding the vertexes and creating the edges which was so tedious that I stopped). But this brought me to this point: Isn't the graph going to have a count of Vertices/Edges that is bigger than a * b * c ?
For example, for only 1 subgraph, I would do this: (I am not doing the complete one, just to demonstrate my thoughts). A, B, C are the sellers. S is the source (no items):
S -> A // connect to A
A -> B|C // connect A to B or C
B -> B|C // connect B to B or C
C -> B|C // connect C to B or C
...
That to mean means roughly:
from S -> Amount of sellers (3)
from each of the sellers node on level 1 -> Amount of sellers (3 * 3)
This continues until the items count goes to zero I believe, at which point it will be *2
This to me means that the graph will have every single combination of ways to calculate things (which will in turn cause duplication and higher complexity). This is because a -> b -> c == c -> b -> a and so on. But how do I determine this when modelling a graph and/or how do I even approach this? I suppose in my algorithm training I never really had to build a graph, but rather got one as an input that I operated upon.
So, summing up, I wonder:
- How do I decide to use Dijkstra's algortihm here?
- How do I translate a table such as above into a graph?
- Isn't iterating over the table and calculating these combinations easier and more efficient than modelling a graph?
- Assuming we use Dijkstra, do we have do construct the graph every single time we want to execute or would that require us to store the information in a graph right away?
For completeness, in Java, this is how I tried to model my graph:
public static void main(String[] args) {
// A 17$ 1 Unit
// B 18$ 3 Units
// C 23$ 5 Units
Graph g = new Graph();
// Nodes
List<Vertex> vertexes = new ArrayList<>();
vertexes.add(v("source", 0, 0.0));
vertexes.addAll(IntStream.range(1, 2).mapToObj(i -> v("A_"+ i, i, 17.0)).collect(Collectors.toList()));
vertexes.addAll(IntStream.range(1, 4).mapToObj(i -> v("B_"+ i, i, 18.0)).collect(Collectors.toList()));
vertexes.addAll(IntStream.range(1, 6).mapToObj(i -> v("C_"+ i, i, 23.0)).collect(Collectors.toList()));
// Sort the nodes by level (e.g. level 1 means buying 1 item from the seller)
Collections.sort(vertexes, new Comparator<Vertex>() {
@Override
public int compare(Vertex o1, Vertex o2) {
return Integer.compare(o1.level, o2.level);
}
});
// connect the vertexes:
for(int i = 0; i< vertexes.size(); i++) {
Vertex s = vertexes.get(i);
for(int j = i+1; j < vertexes.size(); j++) {
Vertex d = vertexes.get(j);
if(d.level == s.level) continue; // same level can't connect as we can not buy 1 and end up with the same count
if(d.level -1 != s.level) break; // level difference > 1 means we would buy 1 and end up with 2 items
Edge e = e(s, d, d.price); // Create the edge from n to n+1 so that we can buy this
g.edges.add(e);
}
}
g.edges.forEach(System.out::println);
g.vertexes.addAll(vertexes);
}
This prints the following graph for me:
<source> to <A_1> Cost 17.0
<source> to <B_1> Cost 18.0
<source> to <C_1> Cost 23.0
<A_1> to <B_2> Cost 18.0
<A_1> to <C_2> Cost 23.0
<B_1> to <B_2> Cost 18.0
<B_1> to <C_2> Cost 23.0
<C_1> to <B_2> Cost 18.0
<C_1> to <C_2> Cost 23.0
<B_2> to <B_3> Cost 18.0
<B_2> to <C_3> Cost 23.0
<C_2> to <B_3> Cost 18.0
<C_2> to <C_3> Cost 23.0
<B_3> to <C_4> Cost 23.0
<C_3> to <C_4> Cost 23.0
<C_4> to <C_5> Cost 23.0
This however is incomplete, it only allows to buy items up to the max amount of items of all sellers. That is why I thought I need a graph that has all combinations of all sellers in any order, so that I can determine any order and their paths.
I hope I managed to write my thoughts/questions down so they make logical sense :) if you find that it is unclear please let me know and I will try and make it a bit clearer.
