knapsack_2.h

/****************************************************************************
  FileName     [ knapsack.h ]
  Synopsis     [ Knapsack Solver ]
  Author       [ Jui-Yang (Tony) Hsu]
  Copyright    [ Copyleft(c) 2017 NTUEE, Taiwan ]
****************************************************************************/

#ifndef KNAPSACK_H
#define KNAPSACK_H

#include <vector>
#include <algorithm>
/**
 * Note: weight type must be integer
**/
namespace knapsack{
  struct Item{
    int value;
    int weight;

    Item(int value=0,int weight=0): value(value),weight(weight){}
  };
  int value_accumulate(const Item& lhs, const Item& rhs){return lhs.value + rhs.value;}
  
  //Given the item list (item w/ weight and value) and capacity constraint
  //Returns an integer vector representing the picked item's id of OPT soltion
  //D{[n,v]: min. weight of picked item (1 ~ n) s.t value >= v
  std::vector<int> knapsack_solver(std::vector<Item>& item_ls, int cap){
    int max_val = std::accumulate(item_ls.begin(),item_ls.end(),0,value_accumulate);

    int num_item = item_ls.size();
    int DP[num_item+1][max_val+1] = {};
    for(int v=1; v<=max_val;++v){
      DP[0][v] = INT_MAX;
    }
    
    for(int n=1;n<=num_item;++n){ 
      for(int v=1;v<=max_val;++v){
        if(v < item_ls[n-1].value)
          DP[n][v] = std::min(item_ls[n-1].weight,DP[n-1][v]);
        else{
          if(DP[n-1][v-item_ls[n-1].value] < INT_MAX)
            DP[n][v] = std::min(DP[n-1][v],DP[n-1][v-item_ls[n-1].value]+item_ls[n-1].weight);
          else
            DP[n][v] = DP[n-1][v];
        }
      }
    }

    std::vector<int> picked_items; picked_items.reserve(num_item);
    int val;
    int n = num_item;
    for (int v = 1; v <= max_val; v++) {
      if(DP[num_item][v] > cap){ // find the border
        val = v-1;
        break;
      }
    }
    
    while(n>=1){ // backtrace the solution
      if(DP[n][val] - DP[n-1][val-item_ls[n-1].value] == item_ls[n-1].weight){
        picked_items.push_back(n-1);
        val -= item_ls[n-1].value;
      }
      n--;
    }
    return picked_items;
  }
}
#endif