交互式Python实验室

0/1 Knapsack DP

Playground在加载时自动运行。点击运行我的代码来追踪你的Python代码 — 每一步实时动画展示。

解释·逐行

回放·逐步

挑战·引导式提示

XP·...

数据流水线

mastery 路径

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

解释

Line 1

knapsack(weights=[2,3,4,5], values=[3,4,5,6], capacity=8) called.

为什么用这种方法？

We have 4 items with given weights and values, and a knapsack capacity of 8. The goal is to find the maximum total value without exceeding the weight limit.

Structured Explanation

Overview

背包问题: 在容量W的包中装入有重量和价值的物品使价值最大。

Analogy

就像旅行者在行李箱限重内装最有价值的旅行装备。

Step-by-step

dp[i][w]=前i件物品重量不超过w的最大价值
空间优化: 用一维dp[w]
每件物品反向更新(0/1情况)
最终答案是dp[W]

Visual

items=[(2kg,3元),(3kg,4元),(4kg,5元)] W=5 dp[5]=max(dp[3]+4, dp[5]) 最终dp: [0,0,3,4,4,7]

Common mistakes

0/1背包内层不反向遍历(导致重复选取)
混淆分数背包

Practice questions

用2D和1D实现0/1背包
转化为目标和(只考虑重量)问题

Time

O(nW)

Space

O(W)

复杂度

时间

O(n × W)

空间

O(n × W)

复杂度概览

O(1)

O(log n)

O(n)

O(n log n)

O(n²)时间空间

n = 8范围 1-20

当 N = 8 时

复杂度	操作
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

挑战

解决0/1背包问题: items=[(2,6),(2,10),(3,12)], capacity=5。逐行构建DP表。

提示

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])。每个单元格是一个子问题。

代码工作室

0/1 Knapsack DP

Monaco就绪

Python就绪

lesson.pyline 1

Loading editor...

输出控制台

1 lines

❯ 10

现实世界应用

1

Cargo shipment payload optimization

2

Investment maximum yield tracking

3

Micro-service CPU load balancing

Comments

Loading comments...