完成任务的最佳途径

Question

为了达到“技能”，我必须完成一定数量的与该技能相关的“任务”。

Skill 1: Need 1 of A, B, C, D, or E 
Skill 2: Need 2 of B, F, or G 
Skill 3: Need 1 of X, Y, or Z 
Skill 4: Need 2 of F or X 

假设所有“任务”的成本是一样的：

Optimal Answer: 
1 Task B 
1 Task F 
1 Task X 

是否有任何建议，一个有效的算法，以帮助找到最佳的输出，当任务并不总是成本相同？

Answer 1

我能够使用@PaulHankin的指导来解决这个问题。这里是使用Google's OR tools的解决方案。

static void Main() 
    { 
     var solver = Solver.CreateSolver("IntegerProgramming", "CBC_MIXED_INTEGER_PROGRAMMING"); 
     // all are integer non-negative variables. 
     var a = solver.MakeIntVar(0.0, double.PositiveInfinity, "a"); 
     var b = solver.MakeIntVar(0.0, double.PositiveInfinity, "b"); 
     var c = solver.MakeIntVar(0.0, double.PositiveInfinity, "c"); 
     var d = solver.MakeIntVar(0.0, double.PositiveInfinity, "d"); 
     var e = solver.MakeIntVar(0.0, double.PositiveInfinity, "e"); 
     var f = solver.MakeIntVar(0.0, double.PositiveInfinity, "f"); 
     var g = solver.MakeIntVar(0.0, double.PositiveInfinity, "g"); 
     var x = solver.MakeIntVar(0.0, double.PositiveInfinity, "x"); 
     var y = solver.MakeIntVar(0.0, double.PositiveInfinity, "y"); 
     var z = solver.MakeIntVar(0.0, double.PositiveInfinity, "z"); 

     // Minimize a + b + c + d + e + f + g + x + y + z 
     var objective = solver.Objective(); 
     objective.SetMinimization(); 
     objective.SetCoefficient(a, 1); 
     objective.SetCoefficient(b, 1); 
     objective.SetCoefficient(c, 1); 
     objective.SetCoefficient(d, 1); 
     objective.SetCoefficient(e, 1); 
     objective.SetCoefficient(f, 1); 
     objective.SetCoefficient(g, 1); 
     objective.SetCoefficient(x, 1); 
     objective.SetCoefficient(y, 1); 
     objective.SetCoefficient(z, 1); 

     // Skill 1: a + b + c + d + e >= 1 
     var skill1 = solver.MakeConstraint(1, double.PositiveInfinity); 
     skill1.SetCoefficient(a, 1); 
     skill1.SetCoefficient(b, 1); 
     skill1.SetCoefficient(c, 1); 
     skill1.SetCoefficient(d, 1); 
     skill1.SetCoefficient(e, 1); 

     // Skill 2: b + f + g >= 2 
     var skill2 = solver.MakeConstraint(2, double.PositiveInfinity); 
     skill2.SetCoefficient(b, 1); 
     skill2.SetCoefficient(f, 1); 
     skill2.SetCoefficient(g, 1); 

     // Skill 3: x + y + z >= 1 
     var skill3 = solver.MakeConstraint(1, double.PositiveInfinity); 
     skill3.SetCoefficient(x, 1); 
     skill3.SetCoefficient(y, 1); 
     skill3.SetCoefficient(z, 1); 

     // Skill 4: f + x >= 2 
     var skill4 = solver.MakeConstraint(2, double.PositiveInfinity); 
     skill4.SetCoefficient(f, 1); 
     skill4.SetCoefficient(x, 1); 

     var resultStatus = solver.Solve(); 

     // Check that the problem has an optimal solution. 
     if (resultStatus != Solver.OPTIMAL) 
     { 
      Console.WriteLine("The problem does not have an optimal solution!"); 
      return; 
     } 

     Console.WriteLine("Problem solved in " + solver.WallTime() + " milliseconds"); 

     // The objective value of the solution. 
     Console.WriteLine("Optimal objective value = " + objective.Value()); 

     // The value of each variable in the solution. 
     Console.WriteLine("a = " + a.SolutionValue()); 
     Console.WriteLine("b = " + b.SolutionValue()); 
     Console.WriteLine("c = " + c.SolutionValue()); 
     Console.WriteLine("d = " + d.SolutionValue()); 
     Console.WriteLine("e = " + e.SolutionValue()); 
     Console.WriteLine("f = " + f.SolutionValue()); 
     Console.WriteLine("g = " + g.SolutionValue()); 
     Console.WriteLine("x = " + x.SolutionValue()); 
     Console.WriteLine("y = " + y.SolutionValue()); 
     Console.WriteLine("z = " + z.SolutionValue()); 

     Console.WriteLine("Advanced usage:"); 
     Console.WriteLine("Problem solved in " + solver.Nodes() + " branch-and-bound nodes"); 
     Console.ReadKey(); 
    }