Solving 0/1 knapsack problem with dynamic programming

Introduction

0/1 knapsack problems

A long time ago, an explorer went to an island where there were treasures, but his knapsack could only hold a maximum weight of \(W\). Each treasure had its corresponding weight \(w_i\) and value \(v_i\). He was very worried about how to maximize the total value of the items in his knapsack

Content

Why can we use dynamic programing(DP) to solve the problem.

• Principle of optimality
• Definition
  • The optimal solution of the problem includes the optimal solution of the subproblem
  • In other words, we can derive the optimal solution of the problem from the optimal solution of the subproblem.
  • For this issue
    • The maximum value of the \(i_{th}\) item with a total weight of \(W\) can be derived from the maximum value of the first \({i-1}_{th}\) item with a weight of \(W - w_i\)
• Without aftereffect
• Definition
  • Once the state of a certain stage is determined, it is not affected by decisions made in subsequent stages
  • For this issue
    • The maximum value at the current weight of \(w\) is still the maximum value at w when the current weight is greater than \(w\).

Why should we use DP

• Faster than depth first search(DFS)
  • Time complexity achieved using DP is just \(\operatorname O(nv)\)
  • Despite extensive optimization, the time complexity of DFS remains high
• Higher accuracy than greedy algorithms
  • Obvious, an item cannot be separated.
  • as long as \(w_i\mod v_i \neq 0\),Greedy algorithms cannot find maximum value.

How to solve the problem by DP

• Define the state
  • We define the state \(F_{i,j}\) as the maximum value that a backpack can hold for the first \(i\) items with a weight of \(j\).
• Derive state transition equation
  • Facing the \(i_{th}\) item, we only have two choice
    • Don't chose the \(i_{th}\) item
      • Obviously, the \(F_{i,j}\) can be transferred from \(F_{i - 1, j}\)
    • Chose the \(i_{th}\) item
      • Consider the weight of the current item
        • We can't chose the item without any weight consumption
        • We need \(w_i\) weight to hold the item
        • then we should transfer from \(F_{i - 1,j - w_i}\)
      • Consider the value of the current item
        • Obviously,when we chose the item, we get \(v_i\) value。
        • then \(F_{i - 1,j - w_i} + v_i\)
      • \(F_{i,j} = \max(F_{i,j}, F_{i - 1, j- w_i} + v_i)\)
• Optimize space consumption
  • Obviously,every \(F_{i,j}\) is transferred from \(F_{i - 1, ?}\)
  • So we don't need to declare a two-dimensional array.
  • Instead of that, we use a one-dimensional array and do reverse enumeration so that we can use the \(i - 1\) state to update the \(i\) state.
• Code implementation

for (int i = 1; i <= M; i++)
{
	for (int j = T; j >= v[i]; j--)
	{
		dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
	}
}    

Conclusion

In a word, use our DP solution to the 0/1 knapsack problem.

You can get:

• Better time complexity
  • save your time
• Better space complexity
  • reduce your space consumption
• Simple code implementation
  • Easy to maintain