There's an ancient Rulial story about a statue two vast and trunkless legs of stone, the Lagos district of the crumbled empire, your article @David Daniel was like hitching a ride on the spacecraft.
benefits = {7, 9, 5, 8, 6, 5};
weights = {3, 4, 1, 3, 5, 2};
vars = Table[Subscript[x, s], {s, 6}];
obj = benefits . vars;
constr1 = weights . vars <= 10;
constr2 = Subscript[x, 1] + Subscript[x, 2] <= 1;
constr3 = Subscript[x, 1] + Subscript[x, 6] <= 1;
constr4 = Subscript[x, 2] + Subscript[x, 3] <= 1;
constr5 = Subscript[x, 3] + Subscript[x, 4] <= 1;
constr6 = Subscript[x, 3] + Subscript[x, 6] <= 1;
constr7 = Subscript[x, 4] + Subscript[x, 5] <= 1;
constr8 = Subscript[x, 5] + Subscript[x, 6] <= 1;
intervals = Thread[0 <= vars <= 1];
{val, point} =
Maximize[{obj, constr1, constr2, constr3, constr4, constr5, constr6,
constr7, constr8, intervals}, vars, Integers]
benefitsValues = benefits*Values[point];
PieChart[benefitsValues,
ChartLabels ->
Table[Labeled["x" <> ToString[i], benefitsValues[[i]]], {i,
Length[benefitsValues]}]]
And I was crying when I heard about the Ruliad because it's just phenomenal like this beautiful graph that we have here solving the Project Allocation Problem (PAP) using the Fractional Knapsack model.
The objective is to maximize the benefit of a set of six projects, and we can do more.
edges = {Labeled[1 -> 2, "x[1]=0"],
Labeled[1 -> 3, "x[1]=1"],
Labeled[2 -> 4, "x[2]=0"],
Labeled[2 -> 5, "x[2]=1"],
Labeled[5 -> 6, "x[3]=0"],
Labeled[5 -> 7, "x[3]=1"],
Labeled[7 -> 8, "x[4]=0"],
Labeled[7 -> 9, "x[4]=1"],
Labeled[9 -> 10, "x[5]=0"],
Labeled[9 -> 11, "x[5]=1"],
Labeled[10 -> 12, "x[6]=0"],
Labeled[10 -> 13, "x[6]=1"]};
Graph[edges,
GraphLayout -> "LayeredEmbedding",
VertexLabels -> Placed["Name", After],
VertexSize -> 0.1,
VertexLabelStyle ->
Directive[FontFamily -> "Alegreya SC", Bold, 16],
EdgeLabelStyle ->
Directive[FontFamily -> "Courier", Bold, 14, Darker[Blue]]
]
And what do you say about the greedy algorithm? Even if we do its bidding, it's amazing because we can make optimal project selections.
Thank you @David Daniel for publishing this version. It's like the way that something would be written today, the cultural difference, that something was put here on purpose, the 0-1 Knapsack problem, a variation of the knapsack problem where each item can be included only once or not at all. We're keeping within the knapsack's capacity so it doesn't weigh that much but it has so many benefits and values.
ClearAll[FractionalKnapsack]
SortByRatio[weights_,
profits_] := {weights, profits}[[All,
Ordering[N[profits/weights], All, Greater]]]
FractionalKnapsack[noOfObjects_, weightsAndprofits_, capacityOfbag_] :=
Module[{x, tp, i, u, weight, profit}, {weight, profit} =
SortByRatio @@ Transpose[weightsAndprofits];
x = ConstantArray[0.0, noOfObjects]; tp = 0; u = capacityOfbag;
For[i = 1, i <= noOfObjects && weight[[i]] <= u, i++, x[[i]] = 1.0;
tp += profit[[i]]; u -= weight[[i]]];
If[i <= noOfObjects, x[[i]] = u/weight[[i]];
tp += x[[i]]*profit[[i]]];
Labeled[BarChart[x, ChartStyle -> 24],
Style["Your Maximum Profit is " <> ToString[N@tp]]]]
weightsAndProfits =
Transpose[{RandomInteger[{1, 20}, numItems = 20],
RandomInteger[{5, 50}, numItems = 20]}];
FractionalKnapsack[numItems, weightsAndProfits, capacity = 50]
@David Daniel the "problem" of indiscriminate allocation of projects by decision-makers, well, it turns out that this graph is actually a beautiful graph for one day, and guess what? The cards are down, and the [WSS22] Fractional Knapsack model for project allocation problem is the physical embodiment of these cards in that the proposed Fractional Knapsack model is completed with efficiency and we can see each aspect of the allocated budget.
The algorithm can be applied to project management problems and we should eagerly be supportive of its inundation, because any amount can guide us through this project like we can @David Daniel with this fantastic adoption of the Fractional Knapsack Algorithm.
