第15周_动态规划_01背包问题_作业

本次OJ评测的主要目的是检验考生对动态规划中的关于01背包问题的应用，主要内容如下：

1. 基本模型

（1）问题描述：给定 n 个物品，第 i 项物品体积为 w[i]，价值为 c[i]，背包容量为 m。每物品最多选一次，求不超容量的最大总价值。

（2）状态定义

- 二维数组：dp[i][j] 表示前 i 个物品在容量 j 时的最大价值。

- 一维数组：dp[j] 表示容量 j 时的最大价值（空间优化）。

（3）状态转移方程：dp[j]=max(dp[j],dp[j−w[i]]+c[i])(j≥w[i])

2. 常见变种问题与处理方法

（1）恰好装满背包：初始化 dp[0] = 0，其余为负无穷（保证只有恰好装满的可行解被更新）。    

（2）求方案总数：状态记录组合数dp[j] += dp[j - w[i]]（初始化 dp[0] = 1）。     

（3）二维费用背包：状态增加第二维度费用，需双重逆序遍历，物品同时消耗体积和重量资源。