sol.cpp

// This problem can be turned into a standard set cover problem.
// https://math.mit.edu/~goemans/18434S06/setcover-tamara.pdf
// https://www.geeksforgeeks.org/set-cover-problem-set-1-greedy-approximate-algorithm/

#include <iostream>
#include <unordered_map>
#include <vector>
#include <set>
#include <algorithm>

// solves the set cover problem by greedy method. This is an approximate solution
int optimumSetCover(std::vector<std::set<int>> setsAvailable, std::vector<int> costs, int num_items){
  int cost_incurred = 0;
  std::set<int> itemsCovered;
  while (itemsCovered.size()<num_items){
    std::vector<double> costRatio(setsAvailable.size()); //cost/(N-I)
    std::cout<<"costs = ";
    for (int i=0; i<setsAvailable.size(); i++){
      // remove items which we already have
      for (int item: itemsCovered) setsAvailable[i].erase(item);
      costRatio[i] = double(costs[i])/double(setsAvailable[i].size());
      std::cout<<costRatio[i]<<' ';
    }
    std::cout<<'\n';
    std::vector<double>::iterator it = std::min_element(costRatio.begin(), costRatio.end());
    int pos = it-costRatio.begin();

    for (int item: setsAvailable[pos]) itemsCovered.insert(item);
    cost_incurred += costs[pos];
    setsAvailable.erase(setsAvailable.begin()+pos);
    costs.erase(costs.begin()+pos);

    std::cout<<"Items Covered = ";
    for (int item: itemsCovered) std::cout<<item<<' ';
    std::cout<<'\n';

  }
  return cost_incurred;
}


void testSetCover(){
  std::vector<std::set<int>> setsAvailable {{4,1,3}, {2,5}, {1,4,3,2}};
  std::vector<int> costs {5,10,3};
  int num_items = 5;
  int optimum_cost = optimumSetCover(setsAvailable, costs, num_items);
  std::cout << "Optimum Cost = " << optimum_cost << '\n';
}

// this function wil turn the problem into set cover problem and then invoke our function
int minDrinkProblem(std::unordered_map<int, std::vector<int>> preferences){
  std::unordered_map<int, std::set<int>> satisfy_drink;
  for (auto item: preferences){
    for (int drink: item.second) satisfy_drink[drink].insert(item.first);
  }
  std::vector<std::set<int>> setsAvailable;
  for (auto item: satisfy_drink) setsAvailable.push_back(item.second);
  std::vector<int> costs(setsAvailable.size(), 1);
  int num_items = preferences.size();
  int optimum_num_drinks = optimumSetCover(setsAvailable, costs, num_items);
  return optimum_num_drinks;
}

void test(){
  std::unordered_map<int, std::vector<int>>
  preferences {
      {0, {0, 1, 3, 6}},
      {1, {1, 4, 7}},
      {2, {2, 4, 7, 5}},
      {3, {3, 2, 5}},
      {4, {5, 8}}
  };
  int optimum_num_drinks = minDrinkProblem(preferences);
  std::cout << "Optimum # of Drinks = " << optimum_num_drinks << '\n';
}

int main(){
  testSetCover();
  test();
  return 0;
}