Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

a variation of 0/1 knapsack.

Revision en1, by zarif_2002, 2018-12-12 11:27:22

when we are asked for solving knapsack problem where i-th item has exactly K_i copies then what to do without merging them into array.

for example, n = 2, V = {100, 30}, W = {17, 10}, K = {3,4}, S = 50. this means you can use item-1 3 times and item-2 4 times. then, i can merge the array as,

V = {100, 100, 100, 30, 30, 30, 30} and W = {17, 17, 17, 10, 10, 10, 10} and then using original knapsack. but that would take a lot of time--- O(S*sum of k).

how can i get a better solution.

Tags knapsack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English zarif_2002 2018-12-12 11:27:22 521 Initial revision (published)