c++ - How do i solve these variations of the 0-1 knapsack algorithm? -

the knapsack can carry maximum weight , max_wt ; has n items given weightwt[] , valueval[].i have 2 questions ( both seperate each other ) :

• what maximum value can carry if there second limit volume carry , vol[ ] ?
• what number of ways carry total of z(< n) items such sum of values divisible number , 8 ?

my attempt

• for first question refered this stackoverflow post , answer understand 1 2 constraints merged ,but run time complexity of quite big guess...what thinking making dp[i][j][k] , number of items selected , j max-wt selected @ point , k max-vol selected @ point , core of code looked
  for(i=0 ; < n ; i++) \\ n no. of items for(j=0 ; j < n ; j++) for(k=0 ; k < n ; k++) dp[i][j][k] = max( dp[i-1][j][k] , val[i] + dp[i-1][j-wt[j]][k-vol[k]]) ;
  , seems alright , gives me wrong answer ... cant guess why :(

• i can't start think of second problem, friend did taking 3 states dp[i][j][k] , j same first question(the usual ones) while 'k' keeps track of total items selected , idea isnt getting in head . plus , state store , stores max value possible till given state in classical knapsack problems , here guess state store total combinations divisible 8 till state , cant convert code .

p.s please try providing solution bottom approach second question , new dynamic programming . ;)

two-dimensional knapsack problem

• let n number of items
• let val[i] value of i-th item
• let w[i] weight of i-th item
• let v[i] volume of i-th item
• let t[i,j,k] best value out of first i items , having exactly weight j , volume k. t can defined in other way definition gives short formula.

finding best value

• t[0,j,k] = 0

• t[i,j,k] = t[i-1,j,k], when j<w[i] or k<v[i], otherwise:

• t[i,j,k] = max( t[i-1,j,k] , t[i-1,j-w[i],k-i] + val[i] )

• best possible value max t[n,j,k] j , k

implementation notes

• initialize base cases first j , k

• loop i 1 n , consistent 1-based arrays indexes

• loop j 1 max possible weight sum of weights, e.g. w[1]+w[2]+...w[n]

• loop k 1 max possible volume

counting number of ways exact value exact number of items

• let s[i,j,k,l] number of ways in first i items can arranged weight j, value k, , l items.

• s[0,j,k,l] = 0, except s[0,0,0,0] = 1

• s[i,j,k,l] = s[i-1,j,k,l] + s[i-1,j-w[i],k-val[i],l-1]

• number of ways value y using z items sum of t[n,j,y,z] j

observations

there many ways @ these problems , define states t , s. 1 of them. implementations can differ. thumb-rule dimensions constraint in sack or dimension in items means dimension in formula. thumb-rule counting ways add instead of finding max.