while digging in itemresource table especially the stats "varX_X" columns
I can see that the stats are combination of base stats id's .
524288, 8192, 65536, 512, 1024, 128, 256, 2048, 4096, 131072, 262144, 268435457, 134217728, 16777216, 268435456, 33554432, 1048576, 16384, 32768, 1, 2, 16, 32, 4, 8, 2097152, 4194304, 64
and each one represents a stat value in game .
for example .
mdef + pdef = 1536
that means 1024 (mdef) + 512 (pdef)
and so on ,
my goal isn't the combination itself ... it's how to reverse it in seconds .
I used this algorithm and it is so slow for large numbers .
any ideas ?
*knapsack problem*
btw: I'm interested in raskim new db manager hoping that he has a solution in it :D
I can see that the stats are combination of base stats id's .
524288, 8192, 65536, 512, 1024, 128, 256, 2048, 4096, 131072, 262144, 268435457, 134217728, 16777216, 268435456, 33554432, 1048576, 16384, 32768, 1, 2, 16, 32, 4, 8, 2097152, 4194304, 64
and each one represents a stat value in game .
for example .
mdef + pdef = 1536
that means 1024 (mdef) + 512 (pdef)
and so on ,
my goal isn't the combination itself ... it's how to reverse it in seconds .
I used this algorithm and it is so slow for large numbers .
Code:
public class Solver {
private List<List<decimal>> mResults;
public List<List<decimal>> Solve(decimal goal, decimal[] elements) {
mResults = new List<List<decimal>>();
RecursiveSolve(goal, 0.0m,
new List<decimal>(), new List<decimal>(elements), 0);
return mResults;
}
private void RecursiveSolve(decimal goal, decimal currentSum,
List<decimal> included, List<decimal> notIncluded, int startIndex) {
for (int index = startIndex; index < notIncluded.Count; index++) {
decimal nextValue = notIncluded[index];
if (currentSum + nextValue == goal) {
List<decimal> newResult = new List<decimal>(included);
newResult.Add(nextValue);
mResults.Add(newResult);
}
else if (currentSum + nextValue < goal) {
List<decimal> nextIncluded = new List<decimal>(included);
nextIncluded.Add(nextValue);
List<decimal> nextNotIncluded = new List<decimal>(notIncluded);
nextNotIncluded.Remove(nextValue);
RecursiveSolve(goal, currentSum + nextValue,
nextIncluded, nextNotIncluded, startIndex++);
}
}
}
}
Code:
class Program {
static void Main(string[] args) {
string input;
decimal goal;
decimal element;
do {
input = "IN COMBINATION";
}
while (!decimal.TryParse(input, out goal));
input = "524288 8192 65536 512 1024 128 256 2048 4096 131072 262144 268435457 134217728 16777216 268435456 33554432 1048576 16384 32768 1 2 16 32 4 8 2097152 4194304 64";
string[] elementsText = input.Split(' ');
List<decimal> elementsList = new List<decimal>();
foreach (string elementText in elementsText) {
if (decimal.TryParse(elementText, out element)) {
elementsList.Add(element);
}
}
Solver solver = new Solver();
List<List<decimal>> results = solver.Solve(goal, elementsList.ToArray());
foreach(List<decimal> result in results) {
foreach (decimal value in result) {
Console.Write("{0}\t", value);
}
Console.WriteLine();
}
Console.ReadLine();
}
}
*knapsack problem*
btw: I'm interested in raskim new db manager hoping that he has a solution in it :D
