% Copyright (C) Daphne Koller, Stanford University, 2012

function [MEU OptimalDecisionRule] = OptimizeMEU( I )

  % Inputs: An influence diagram I with a single decision node and a single utility node.
  %         I.RandomFactors = list of factors for each random variable.  These are CPDs, with
  %              the child variable = D.var(1)
  %         I.DecisionFactors = factor for the decision node.
  %         I.UtilityFactors = list of factors representing conditional utilities.
  % Return value: the maximum expected utility of I and an optimal decision rule
  % (represented again as a factor) that yields that expected utility.

  % We assume I has a single decision node.
  % You may assume that there is a unique optimal decision.
  D = I.DecisionFactors(1);

  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  %
  % YOUR CODE HERE...
  %
  % Some other information that might be useful for some implementations
  % (note that there are multiple ways to implement this):
  % 1.  It is probably easiest to think of two cases - D has parents and D
  %     has no parents.
  % 2.  You may find the Matlab/Octave function setdiff useful.
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

  EUF = CalculateExpectedUtilityFactor(I);
  OptimalDecisionRule = struct('var', EUF.var, 'card', EUF.card, 'val', []);

  [randVar, indxRandVar] = setdiff(EUF.var, D.var(1), "stable");
  [Dvar, indxDvar] = intersect(EUF.var, D.var(1), "stable");
  decision_number = prod(EUF.card(indxRandVar));

  if isempty(indxRandVar)
    [MEU, idxMEU] = max(EUF.val);
    lista = zeros(1, EUF.card);
    lista(idxMEU) = 1;
    OptimalDecisionRule.val = lista;
    return;
  endif

  max_list = -Inf * ones(1, decision_number);
  for i = 1:prod(EUF.card)
    as = AssignmentToIndex( IndexToAssignment(i, EUF.card)(indxRandVar), EUF.card(indxRandVar) );
    max_list(as) = max(max_list(as), EUF.val(i));
  endfor

  MEU = sum(max_list);

  for i = 1:prod(EUF.card)
    as = AssignmentToIndex( IndexToAssignment(i, EUF.card)(indxRandVar), EUF.card(indxRandVar) );
    if (EUF.val(i) == max_list(as))
      OptimalDecisionRule.val(i) = 1;
    else
      OptimalDecisionRule.val(i) = 0;
    endif
  endfor

end
