Introduction to Complete Knapsack Problem

In [here], the basic 0/1 knapsack is discussed. For each item, you can choose to put or not to put into the knapsack. Therefore, for the number of items, there are only two options: 0 or 1.

ks Introduction to Complete Knapsack Problem

In Complete Knapsack Problem, for each item, you can put as many times as you want. Therefore, if capacity allows, you can put 0, 1, 2, $tex_77ac3389da07150817bc1c8af2548a0c Introduction to Complete Knapsack Problem$ items for each type. The Complete Knapsack Problem can also be modelling using 0/1 Knapsack.
>
$tex_94de74945919a29cda0776863be83402 Introduction to Complete Knapsack Problem$

Similar to 0/1 Knapsack, there are O(WN) states that need to be computed. However, for the 0/1 knapsack, the complexity of solving each state is constant. The Complete Knapsack needs $tex_9820f9cba9f4ac9badd4106ec2b15a49 Introduction to Complete Knapsack Problem$ for each state. The total complexity can be considered as $tex_bb598a04d1ab3f9dda80a03abbecfffd Introduction to Complete Knapsack Problem$

One greedy optimisation is to replace items of heavier-but-less-valuable items with ones of lighter-more-valuable. If $tex_672d9ca6ddfba729489d5e039f94b4a4 Introduction to Complete Knapsack Problem$ and $tex_59dabb0515410662e15e8ff1d754332a Introduction to Complete Knapsack Problem$ we can simply and safely use item j instead of item i. This optimisation process can be done in $tex_8fb1f5024a605dc7737c61a8a376e067 Introduction to Complete Knapsack Problem$ time.

Another straightforward transform to 0/1 Knapsack Problem is to consider the maximum number of times for item i to put is $tex_e5d5ba25e8683f4d273529a728e09660 Introduction to Complete Knapsack Problem$ . Therefore, we can treat item i as [/math] w / w_i [/math] items that are of same weight w_i. This does not increase time complexity: by simply splitting one item into many.

The other better transform is to split item i to items that have weights $tex_3e15f9d58a33a3d9ce8db974455b8e1d Introduction to Complete Knapsack Problem$ and values $tex_131e255da024fd28b40da9fc2d35dbc2 Introduction to Complete Knapsack Problem$ for $tex_ca57e96bf639f4918bf1e2033853a070 Introduction to Complete Knapsack Problem$ . This is based on binary. No matter how many items we choose, we can represent the total number as the sum of many $tex_7405a79fabe456769d59cb55944c978d Introduction to Complete Knapsack Problem$ sub-items. This splitting yields $tex_d5aa2620e60cbaeb56694d9397b8d7e9 Introduction to Complete Knapsack Problem$ .