DP 背包问题详解pdf
139 浏览量
2024-05-19
10:17:28
上传
评论
收藏 320KB PDF 举报
1
背
包
问题
基
本
模
板
背
包
完
全
背
包
多
重
背
包
分
组
背
包
练
习
做
法
：
定
义
dp[i][j]
：
前
i
个
物
品
，
占
⽤
了
不
超
过
j
个
单
位
的
体
积
，
最
多
能
拿
到
多
少
价
值
。
可
得
转
移
⽅
程
：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
复
杂
度
即可
解
决
。
可
以使
⽤
滚
动
数
组
优
化
空
间
，
注
意
内
层
循
环
要
从
⼤
到
⼩
。
模
板
：
P1048
做
法
：
定
义
dp[i][j]
：
前
i
个
物
品
，
占
⽤
了
不
超
过
j
个
单
位
的
体
积
，
最
多
能
拿
到
多
少
价
值
。
可
得
转
移
⽅
程
：
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
复
杂
度
即可
解
决
。
可
以使
⽤
滚
动
数
组
优
化
空
间
，
注
意
内
层
循
环
要
从
⼩
到
⼤
。
模
板
：
P1616
基
本
模
板
01
背
包
有
个
物
品
，
每
个
物
品
的
体
积
是
，
价
值
是
，
拿
⾛
体
积
之
和
不
超
过
的
物
品
，
最
多
能
拿
到
多
少
价
值
。
完
全
背
包
有
种
物
品
，
每
种
物
品
有
⽆
限
个
，
第
种
物
品
的
每
个
物
品
体
积
是
，
价
值
是
，
拿
⾛
体
积
之
和
不
超
过
的
物
品
，
最
多
能
拿
到
多
少
价
值
。
n v
i
w
i
V
O(nV )
n i v
i
w
i
V
O(nV )
资源评论
