0/1 - Knapsack and similar problem on 2D Matrix

Question

Problem: Given a 2d matrix of item weights, their respective costs in another 2d matrix, and max capacity W. Find the optimal selection such that profit is maximum(i.e sum of costs is maximum) and total items weight remains within capacity.

---

Now, Another constraint is you are allowed to choose only a single item from each column **c**or choose no item from that column.

This post has been answered, Solution:

        int Optimal(int available, int currIdx){

        if(currIdx>=n)
        return 0;

        if(DP[available][currIdx] !=-1)
        return DP[available][currIdx];

        if(currIdx == n-1)
        {
            int mx = 0;
            for(int i=0;i<n;i++)
            {
                if(available - c[i][currIdx]>=0) 
                mx = max(mx , w[i][currIdx]);
            }
        return mx;
        }


        int mx = 0;
        for(int i=0;i<n;i++){

        int x = 0,y= 0;

        x = Optimal(available , currIdx +1);  //Don't include current
        if(available - c[i][currIdx] >=0)   
        {
            y = w[i][currIdx] +  Optimal(available - c[i][currIdx] , currIdx+1);// include current
        }

        mx = max( mx,max(x,y));    

        }

        return DP[available][currIdx] =  mx;
        }

Answer 1

For the modelling

Define : $$x_{ij}= \begin{cases} 1 & \mbox{if } \mbox{ element at position $ij$ in the matrix is selected} \\ 0 & \mbox{otherwise } \end{cases}$$

So you want to find :

$$\max \:\: \sum_{i=0}^N\sum_{j=0}^M{c_{ij}x_{ij}}$$

subject to : $$\sum_{i=0}^N{x_{ij}} \leq 1 \:\: \forall j$$

$$\sum_{i=0}^N\sum_{j=0}^M{w_{ij}x_{ij}} \leq W$$

For the algorithm

If you want an easier approach than simplex algorithm try with a simple backtracking algorithm, in which you compare current combination cost with current maximum and you get back in recursion when you arrive at $W' \geq W$; it's better than comparing every combination

Answer 2

The proper way to model a knapsack problem is that you got $N$ items with weights $w_{ij}$ and costs $c_{ij}$ then to maximize profit given a capacity constraint by choosing only a single item from each column, you should solve the following binary linear program \begin{equation*} \begin{aligned} & \underset{x}{\text{maximize}} & & \sum\limits_{i=1}^N\sum\limits_{j=1}^N c_{ij}x_{ij} \\ & \text{subject to} & & \sum\limits_{i=1}^N\sum\limits_{j=1}^N w_{ij}x_{ij} \leq W \\ & & & \sum\limits_{i=1}^N x_{ij} \leq 1 \quad \forall j = 1 \ldots M \\ & & & x_{ij} \in \lbrace 0,1 \rbrace \end{aligned} \end{equation*} A common relaxation here is to drop the binary constraint and solve the linear program \begin{equation*} \begin{aligned} & \underset{x}{\text{maximize}} & & \sum\limits_{i=1}^N\sum\limits_{j=1}^N c_{ij}x_{ij} \\ & \text{subject to} & & \sum\limits_{i=1}^N\sum\limits_{j=1}^N w_{ij}x_{ij} \leq W \\ & & & \sum\limits_{i=1}^N x_{ij} \leq 1 \quad \forall j = 1 \ldots M \end{aligned} \end{equation*} You can use methods such as Simplex or the dual simplex and so on.