Article From:

knapsack problem”

A backpack total capacity of V, now N items, I item capacity of weight[i], the value of value[i], now pack things inside the backpack, how to make the pack in the total value of the goods in the pack, mainly divided into 3 categories:
1. 0-1Knapsack, each item can only take 0, or 1.
2. Complete knapsack, every item can be taken indefinitely.
3. Multiple knapsack, each item has a number of restrictions, the most I items can be num[i].

solution thinking”

Using the method of dynamic programming (dynamic programming), the optimal value of the current state can be transformed into the optimal value of the previous state, and the best value is obtained from the combination of the previous state to the current state cost. F[i] represents the optimal value of the current state, f[i-1The best value of the last state is expressed. S (i-1, I) represents the cost of transferring the state I from the state I-1. Then: f[i] = max{f[j], f[j]+s (i-1, I)}

classification of specific problems

Knapsack problem can be restricted according to the number of items. There are many cases of 0-1 knapsack, complete backpack and multiple knapsack.

0-1 knapsack problem”

0-1Knapsack means that each item has only 0 states or 1 states. It
Define the state with sub problems: that is, f[i][j] represents the maximum value that a I can be placed in a container with J before. The state transfer equation is:
f[i][j] = max{f[i-1][j], f[i-1][j-weight[i]]+value[i]} 
CThe code is implemented as follows:

1     for(int i=1;i<=n;i++)        // i、nThe number of items, the number of the total articles, respectively2     {
3         for(int j=m;j>=0;j--)    // j、mRepresenting the remaining capacity and the total capacity4         {
5             if(j>=weight[i])     // weight[i]Representing the quality of the item I6                 f[j]=max(f[j],f[j-weight[i]]+v[i]);   // v[i] The volume of the item I7         }
8     }


Leave a Reply

Your email address will not be published. Required fields are marked *