Integer Knapsack Problem( Duplicate items permitted) | HackerEarth Academy

Integer Knapsack Problem( Duplicate items permitted) | HackerEarth Academy
You have n types of items, where the i^th item type has an integer size s_i and a real value v_i. You need to fill a knapsack of total capacity C with a selection of items of maximum value. You can add multiple items of the same type to the knapsack.
Let M(j) denote the maximum value you can pack into a size j knapsack.

int knapsack(int value[],int weight[],int n,int C, vector<int> backtrack)
{
 int * M = new int[C+1];
 int i,j,tmp=0,pos=0;
 M[0]=0;
 for(i=1;i<=C;i++)
 {
  M[i] = M[i-1]; // M[i] can be atleast M[i-1]
  pos = i-1 //pos stores the i-weight[j] is the weight filled already if j is the last item added to kanpsack (used to find items in backtracking)
  for(j=0;j<n;j++)
  {
    if(i>=weight[j])
      tmp = M[i-weight[j]]+value[j];
    if(tmp>M[i])
    {
      M[i]=tmp;
      pos = i-weight[j];
    }

  }  
  backtrack.push_back(pos);// after finding the optimal value push its pos
 }
 int ans = M[C];  
 delete[] M;        
 return ans;

}

http://guitarpenguin.is-programmer.com/posts/32172.html

Let  denote the maximum value you can pack into a size  knapsack.

We can express recursively in terms of solutions to smaller problems as follows:




Computing each value will require  time, and we need to sequentially compute such values.
Therefore, total running time is  . Total space is  .

The value of  will contain the value of the optimal knapsack packing.

We can reconstruct the list of items in the optimal solution by maintaining and following “backpointers”

Also check http://tech-queries.blogspot.com/2011/04/integer-knapsack-problem-duplicate.html
http://times.imkrisna.com/2010/05/unbounded-knapsack-java-source-code/

http://yuanhsh.iteye.com/blog/2172349

A thief breaks into a house. Around the thief are various objects: a diamond ring, a silver candelabra, a Bose Wave Radio (tm), a large portrait of Elvis Presley painted on a black velvet background (a "velvet-elvis"), and a large tiffany crystal vase. The thief has a knapsack that can only hold a certain capacity. Each of the items has a value and a size, and cannot hold all of the items in the knapsack.

Item	Size	Value
1 - ring	1	15
2 - candelabra	5	10
3 - radio	3	9
4 - elvis	4	5

1. public int integerKnapsack(int[] weights, int[] values, int capacity) {  
2.     int[][] d = new int[weights.length+1][capacity+1];  
3.     for(int i=1; i<=weights.length; i++) {  
4.         for(int j=1; j<=capacity; j++) {  
5.             if(weights[i-1] > j) {  
6.                 d[i][j] = d[i-1][j];  
7.             } else {  
8.                 d[i][j] = Math.max(d[i-1][j], d[i-1][j-weights[i-1]]+values[i-1]);  
9.             }  
10.         }  
11.     }  
12.     return d[weights.length][capacity];  
13. }

Read full article from Integer Knapsack Problem( Duplicate items permitted) | HackerEarth Academy