0-1 Knapsack

Textbook

Description:

Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. In other words, given two integer arrays val[0..n-1] and wt[0..n-1] which represent values and weights associated with n items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item, or don’t pick it (0-1 property).

Example:

vector<int> val = {60, 100, 120};
vector<int> wt = {10, 20, 30};
int  W = 50;

Output: 100 + 120 == 220;

Idea:

Note

If a item can be chosen multiple times， 就会跟cut rod很像:
m[0]=0
m[w]=max(vi + m[w-wi])

但是只能选一次，则：
m[0, w] = 0
m[i, w] = m[i-1, w] if wi>w
m[i, w] = max(m[i-1, w], m[i-1, w-wi] + vi) if wi<=w

也通过这个练下Provide user hash function to create pair<int, int> as hash map key. 其实DP完全可以用table[m][W+1]来传递，用hash map是练手。

To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set. Therefore, the maximum value that can be obtained from n items is max of following two values. 1) Maximum value obtained by n-1 items and W weight (excluding nth item). 2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).

If weight of nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.

knapSack(wt, val, m-1, W, hash_table) =
max(knapSack(wt, val, m-1, W, hash_table),
    knapSack(wt, val, m-1, W-wt[m-1], hash_table)+val[m-1]);

Code:

Method 1, 用array来memo

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int knapsackHelper(int totalWt, int k, vector<vector<int>>& memo, const vector<int>& wt, const vector<int>& price){
    if(memo[totalWt][k] != -1){
        return memo[totalWt][k];
    }

    if(k==0 || totalWt==0){
        memo[totalWt][k]=0;
        return 0;
    }

    int result;
    if(wt[k-1]<=totalWt){
        result = max(knapsackHelper(totalWt, k-1, memo, wt, price), 
                    knapsackHelper(totalWt-wt[k-1], k-1, memo, wt, price)+price[k-1]);
    }
    else{
        result = knapsackHelper(totalWt, k-1, memo, wt, price);
    }

    memo[totalWt][k]=result;
    return result;
}

int knapsack(int totalWt, const vector<int>& wt, const vector<int>& price){
    int sizeN=wt.size();
    vector<vector<int>> memo(totalWt+1, vector<int>(sizeN+1, -1));

    return knapsackHelper(totalWt, sizeN, memo, wt, price);
}

int main(){
    vector<int> weight = {10,20,30};
    vector<int> price = {60,100,120};

    cout<<knapsack(50, weight, price)<<endl;
}

Method 2, 用hashtable来memo

#include <iostream>
#include <functional> // Define hash function 
#include <vector>
#include <unordered_map>
using namespace std;

struct pair_hash{
    size_t operator()(pair<int, int> const & key) const{
        size_t h1 = hash<int>{}(key.first);
        size_t h2 = hash<int>{}(key.second);
        return h1 ^ (h2<<1); // Not the best way, better using boost::hash_combine
        }
};

// 这个有问题，还没搞定用lambda作为template的parameter
//
// auto pair_hash = [](pair<int, int> const & key){
//         size_t h1 = hash<int>{}(key.first);
//         size_t h2 = hash<int>{}(key.second);
//         return h1 ^ (h2<<1); // Not the best way, better using boost::hash_combine
//     };

// int knapSack(vector<int> &wt, vector<int> &val, int m, int W, unordered_map<pair<int, int>, int, pair_hash> & hash_table){
int knapSack(vector<int> &wt, vector<int> &val, int m, int W, unordered_map<pair<int, int>, int, pair_hash> & hash_table){

    pair<int, int> pair_key={m, W};
    if(hash_table.find(pair_key) != hash_table.end()){
        return hash_table[pair_key];
    }

    if(m==0 || W==0){
        hash_table[pair_key]=0;
        return 0;
    }

    if(wt[m-1]>W){
        return knapSack(wt, val, m-1, W, hash_table);
    }

    hash_table[pair_key] = max(knapSack(wt, val, m-1, W, hash_table),
                                      knapSack(wt, val, m-1, W-wt[m-1], hash_table)+val[m-1]);

    return hash_table[pair_key];
}

int knapSack(vector<int> &wt, vector<int> &val, int m, int W){
    unordered_map<pair<int, int>, int, pair_hash> hash_table;  // DP

    int result = knapSack(wt, val, m, W, hash_table);

    for(auto e: hash_table){
        cout<<'('<<e.first.first<<" "<<e.first.second<<")->"<<e.second<<' ';
    } cout<<'\n';

    return result;
}


int main()
{
    vector<int> val = {60, 100, 120};
    vector<int> wt = {10, 20, 30};
    int  W = 50;

    int m=val.size();

    printf("Money is %d\n", knapSack(wt, val, m, W));
    return 0;
}