2

The knapsack can carry a maximum weight , say max_wt ; has n items with a given weightwt[] and a valueval[].I have two questions ( both seperate from each other ) :

  • What is the maximum value we can carry if there was a second limit to the volume we could carry , vol[ ] ?
  • What are the number of ways to carry a total of exactly z(< n) items such that their sum of values is divisible by a number , say 8 ?

My Attempt

  • For the first question i refered this stackoverflow post , but the only answer i could understand was one where the two constraints were merged ,but the run time complexity of that would be quite big i guess...what i was thinking was making a dp[i][j][k] , where i is the number of items selected , j is the max-wt selected at that point , k is the max-vol selected at that point and then my core of the code looked like
    for(i=0 ; i < n ; i++) \\ n is 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]]) ;
    , this seems alright , but gives me wrong answer ... i cant guess why :(

  • I can't start to think of the second problem, my friend did it by taking three states dp[i][j][k] where i and j are just same as first question(the usual ones) while 'k' keeps track of the total items selected , this idea isnt getting in my head . Plus , what will a state store , it usually stores max value possible till given state in classical knapsack problems , here i guess a state will store total combinations divisible by 8 till that state , but i cant convert this into code .

p.s please try providing a solution with bottom up approach to the second question , i am very new to dynamic programming . ;)

Community
  • 1
  • 1
95_96
  • 341
  • 2
  • 12
  • _What is the maximum number of ways..._ - do you mean just the number of ways? If not, what does maximum refer to? – Gassa Jul 21 '16 at 22:06
  • "such that their sum is divisible by a number" - sum of what? the weight/volume or something else? – Daniel Rodriguez Jul 21 '16 at 22:09
  • sorry , i get the question is unclear , here's the question again in its entirity : given var[ ] , wt[ ] of n items , how do we select exactly z( < n) for our knapsack such that the value is divisible by a number (here 8 ) , it is seperate from the other question and has no volume ...thanks – 95_96 Jul 21 '16 at 22:20
  • @DanielRodriguez sum of value , just the value there is no volume constraint for the second question – 95_96 Jul 21 '16 at 22:21
  • @Gassa i worded it wrongly..i meant just the number of ways...thank you for picking that out – 95_96 Jul 21 '16 at 22:21
  • And then there's `val[]` vs `vol[]`...People here won't be very inclined to help you if you can't present the problem better than this. – TonyK Jul 21 '16 at 22:37
  • @TonyK `vol[ ]` is array of volume of first n elements , `val[ ]` is array of value of first n elements , `wt[ ]` is array of weight of first n elements .Ask any other doubt if you have....and pls give the question a shot . – 95_96 Jul 21 '16 at 22:59

1 Answers1

4

Two-dimensional knapsack problem

  • let n be the number of items
  • let val[i] be the value of the i-th item
  • let w[i] be the weight of the i-th item
  • let v[i] be the volume of i-th item
  • let T[i,j,k] be the best value out of the first i items and having exactly weight j and volume k. T can be defined in some other way but this definition gives a 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 would be max T[n,j,k] for all j and k

Implementation notes

  • initialize base cases first for all j and k

  • loop i from 1 to n and be consistent with 1-based arrays indexes

  • loop j from 1 to max possible weight which is the sum of all weights, e.g. w[1]+w[2]+...w[n]

  • loop k from 1 to max possible volume

Counting number of ways to get an exact value with an exact number of items

  • let S[i,j,k,l] be the number of ways in which the first i items can be arranged with exactly weight j, value k, and 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 to get exactly value y using exactly z items is the sum of T[n,j,y,z] for all j

Observations

There are many ways to look at these problems and to define the states T and S. This is but one of them. Implementations can also differ. The thumb-rule for dimensions is that another constraint in the sack or dimension in the items means another dimension in the formula. The thumb-rule for counting ways is that you add up instead of finding max.

Daniel Rodriguez
  • 607
  • 6
  • 11
  • Call "the number ... (e.g. 8)" for the second question q. You can save memory in the second DP by restricting `k` to the range 0 .. q-1 and doing all arithmetic operations on `k` mod q. – j_random_hacker Jul 22 '16 at 13:18
  • Nice answer...could you please explain the last line though ...I don't understand how `S[i,j,k,l] = S[i-1,j,k,l] + S[i-1,j-w[i],k-val[i],l-1]` counts the total number of ways....from my understanding ,you made s[0,0,0,0] equal to 1 so that whenever that state is reached , the number of count is increased , but I am not sure if I am right . Plus what is the difference between `T[ ]` and `S[ ]` , there was no mention of `T[ ]` for second problem... – 95_96 Jul 22 '16 at 18:10
  • `S[i,j,k,l]` either has the `i`-th item or it doesn't. The number of ways to get to state (i,j,k,l) is the number of ways to get there using the `i`-th item plus the number of ways to get there not using the `i`-th item. The counting problem doesn't care about maximizing value (T), just the number of ways to get an specific value, that's why value is a dimension. – Daniel Rodriguez Jul 22 '16 at 18:28