CODEWITHSUNDEEP
c++algorithmdynamic-programmingbacktrackingknapsack-problem
Chapi
Chapi

Reputation: 85

Multiple Constrain Knapsack

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>:

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:

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!

Upvotes: 2

Views: 716

Answers (1)

Alireza
Alireza

Reputation: 1038

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.

Upvotes: 2

Related Questions