526互联

Solving 0/1 knapsack problem with dynamic programming （英语课汇报）

发布时间 2023-11-20 17:14:43作者: 加固文明幻景

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
    • save your space consumption
  • Simple code implementation
    • Easy to maintain