Multiple Constrain Knapsack

Question

I'm trying to solve the following problem:

INPUT:

1. An array of items, each item has 3 different weights (integers), a value and the amount available of this type of item.
2. A maximum for each type of weight

OUTPUT:

1. An array that tells how many of each item to take in order to achieve the maximum value. The sum of each of the weights of every item must not exceed the maximum allowed and you may not take more of an item of what is available.

Example output: {3,0,2,1} means 3 of item1, 0 of item2, 2 of item3, and 1 of item4.

Example scenario:

In case I wasn't very clear with the explanation, imagine it's about putting food on a backpack. Each type of food has a weight, a volume, a number of calories and a value and there's a certain amount of each type of food available. The objective would be to maximize the value of the food in the backpack without exceeding a certain maximum amount of weight, volume and calories.

On this scenario the INPUT could be:

Array<Food>:

• Burger (Weight 2, Volume 2, Calories 5, Value 5$, number of Burgers 3)
• Pizza (Weight 3, Volume 7, Calories 6, Value 8$, number of Pizzas 2)
• Hot Dog (Weight 1, Volume 1, Calories 3, Value 2$, number of Hot Dogs 6)

int MaxWeight = 10; int MaxVolume = 15; int MaxCalories = 10;

My Attempt

Since the data set is quite small (say 7 types of items and there's no more than 15 pieces of each item available), I thought of a brute force search:

• Keep track of the best set found so far (Most value and doesn't exceed any limits), call best set B
• Have a recursive function R(s) which takes a set (array of how many of each item) as input, if the input is invalid, it returns. If the input is valid it first updates B (in case s better than B) and then calls R(s + p_i) for every product p_i

The idea is to first call R(s) with s = empty set (0 for every product) and every possible branch will be created while the branches that exceed the weights are ignored.

This obviously didn't work cause the amount of branches that have to be checked is huge even for only as few as 7 items

Any help is much appreciated!

Answer 1

You have to consider each type of weight in your DP method. I'll write the implementation in C++:

vector<Food> Array;
int memo[MAX_ITEM][MAX_WEIGHT1][MAX_WEIGHT2][MAX_WEIGHT3];
int f(int ind, int weight1, int weight2, int weight3){
    if(weight1<0 || weight2<0 || weight3<0) return -INF;
    if(ind == Array.size()) return 0;
    int &ret= memo[ind][weight1][weight2][weight3];
    if(ret>0) return ret;
    int res = 0;
    for(int i=0;i<=Array[ind].maxOfType;i++)
        res = max(res, i * Array[ind].value + f(ind+1, weight1-i*Array[ind].weight1, weight2-i*Array[ind].weight2, weight3-i*Array[ind].weight3));
    return ret = res;
}

The DP function is recursive and we use memoization to optimize it. It returns the maximum value we can get. you can call it by:

f(0,MaxWeight1, MaxWeight2, MaxWeight3);

After that we have to track and see which items leads to maximum value. The Next method will print what you want:

void printResult(int ind, int weight1, int weight2, int weight3){
        if(ind == Array.size()) return;
        int maxi = memo[ind][weight1][weight2][weight3];
        for(int i=0;i<=Array[ind].maxOfType;i++){
            int cur = i * Array[ind].value + f(ind+1, weight1-i*Array[ind].weight1, weight2-i*Array[ind].weight2, weight3-i*Array[ind].weight3);
            if(cur == maxi){
                cout<<i<<", ";
                printResult(ind+1, weight1-i*Array[ind].weight1, weight2-i*Array[ind].weight2, weight3-i*Array[ind].weight3);
                break;
            }
        }
}

All codes are tested and works well.