本文是针对背包九讲2.0的学习笔记。

01背包问题

问题定义：

给定n个物体和一个背包，物品i的重量是w_i，价值v_i，背包容量为C，物品只能选择不装或装入背包，问如何选择装入背包的物品，使装入背包中的物品的总价值最大？

形式描述：

输入：C>0，w_i>0，v_i>0，1≤i≤n

输出：（x_1，x_2，…，x_n），$ x_i \in \{0,1\} $，满足$\sum_{1 \le i \le n}w_i$，$x_i \le C$，使得$\sum_{1 \le i \le n}v_ix_i$最大

状态转移：$F[i,v]=max\{F[i-1,v],F[i-1,v-C_i]+W_i\}$(仅考虑第$i$件物品放或者不放）

但在我们实际使用的状态方程中，往往是没有$i$这个参数的【其实表示两个参数的状态转移函数的复杂度以及如何去除i都困扰过我】

初始化时，若只要求装满背包，$F[0]$设为0，其余均设为$-\infty$，如果不要求背包装满，只希望价格最大，初始化全为0。【是否为合法解的区别】

事实上，这要求在每次主循环中我们以$v \leftarrow V \dots 0$的递减顺序计算$F[v]$，这样才能保证计算$F[v]$时，$F[v-C_i]$保存的是状态$F[i-1,v-C_i]$的值

背包九讲——学习笔记（一）

原文：https://www.cnblogs.com/KimLee1895/p/12769997.html