0-1背包

给定n种物品和一背包。物品i的重量是$\omega _i$，其价值为$c_i$，背包的容量为V。问应如何选择装入背包中的物品，使得装入被保重物品的总价值最大？

在选择装入背包的物品时，对每种物品i只有两种选择，即转入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包。

此问题的形式描述是，给定$V \gt 0,\omega _i \gt 0,c_i \gt 0 (1 \leq i \leq n)$，要求找出一个n元0-1向量$(x_1,x_2,…x_n),x_i \in \{0,1\} (1 \leq i \leq n)$，使得$\sum_{i=1}^n w_i x_i \leq V
$，而且$\sum_{i=1}^n c_i x_i$达到最大。因此，0-1背包是一个特殊的整数规划问题：

$$\max \sum_{i=1}^n c_i x_i \quad
\begin{cases}
\sum_{i=1}^n w_i x_i \leq c, \\
x_i \in \{0, 1\}, \quad 1 \leq i \leq n
\end{cases}
$$

算法：

递推：

dp[i][v]表示前i件物品（1≤i≤n,0≤v≤V）恰好装入容量为v的背包中所能获得的最大价值。

考虑对i件物品的选择策略:

1、不放第i件物品，那么问题转化为前i-1件物品恰好装入容量为v的背包中所能获得 的最大价值，也即dp[i-1][v]

2、放第i件物品，那么问题转化为前i-1件物品恰好装入容量为v-w[i]的背包中所能获得的最大价值，也即dp[i-1][v-w[i]]+c[i]

$$ dp[i][v]=max\left\{dp[i-1][v],dp[i-1][v-w[i]]+c[i]\right\}$$

$$(1\le i \le n ,w[i]\le v\le V)$$

滚动数组：

$$ dp[j]=max\left\{dp[j],dp[j-w[i]]+c[j]\right\} $$

填dp时从后往前遍历，防止数据被覆盖。

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 100;//物品最大件数
const int maxv = 1000;//V的上限

int w[maxn], c[maxn], dp[maxv];
int main() {
    int n, V;
    cin >> n >> V;
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    //边界
    for (int v = 0; v < V; v++) {
        dp[v] = 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int v = V; v >= w[i]; v--) {
            //状态转移方程
            dp[v] = max(dp[v], dp[v - w[i]] + c[i]);
        }
    }
    //寻找dp[0...V]中最大的即为答案
    int max = 0;
    for (int v = 0; v <= V; v++) {
        if (dp[V] > max) {
            max = dp[v];
        }
    }
    cout << max;
}

完全背包

有n种物品，每种物品的单件重量为$\omega _i$，价值为$c_i$。现有一个容量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品都有无数件。

整数线性规划问题:

$$
\max \sum_{i=1}^n c_i x_i \quad
\begin{cases}
\sum_{i=1}^n \omega _i x_i \leq b, \\
x_i \text{ 为非负整数}, \quad 1 \leq i \leq n
\end{cases}
$$

算法：

dp[i][v]表示前i件物品（1≤i≤n,0≤v≤V）恰好装入容量为v的背包中所能获得的最大价值。

递推：

考虑对i件物品的选择策略:

1、不放第i件物品，那么dp[i][v]=dp[i-1][v],这步和01背包是一样的。

2、放第i件物品，不同于01背包，而是转移到dp[i][v-w[i]]，这是因为每种物品可以放任意件（注意有容量限制，因此还是有限的），放了第i件物品后还可以继续放第i件物品，直到第二维的v-w[i]无法保持大于等于0为止。

$$ dp[i][v]=max\left\{dp[i-1][v],dp[i][v-w[i]]+c[i]\right\}$$

$$(1\le i \le n ,w[i]\le v\le V)$$

边界：$dp[0][v]=0(0\le v\le V)$

状态转移方程：

$$ dp[j]=max\left\{dp[j],dp[j-w[i]]+c[j]\right\} $$

形成一维后和01背包完全相同，唯一的区别在于这里v的枚举顺序是正向枚举。

二维0-1背包问题

给定n种物品和一个背包。物品i的重量是$\omega _i$，体积是$b_i$，其价值为$c_i$，背包的容量为V，体积为D，问应如何选择装入背包中的物品，使得装入背包中的物品的总价最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包，。不能将物品i装入背包多次，也不能装入部分的物品。

该问题是二维 0-1 背包问题。问题的形式化描述是：给定 $V > 0$，$D > 0$，$\omega _i > 0$，$b_i > 0$，$c_i > 0$（$1 \leq i \leq n$），要求找出 $n$ 元 0-1 向量 $(x_1, x_2, \dots, x_n)$，其中 $x_i \in \{0, 1\}$ （$1 \leq i \leq n$），使得：$\sum_{i=1}^n w_i x_i \leq V $，$ \quad \sum_{i=1}^n b_i x_i \leq d$,而且$\sum_{i=1}^n v_i x_i$达到最大。

整数规划问题：

$$
\max \sum_{i=1}^n v_i x_i \quad
\begin{cases}
\sum_{i=1}^n w_i x_i \leq c, \\
\sum_{i=1}^n b_i x_i \leq d
\end{cases}, \quad
x_i \in \{0, 1\}, \ 1 \leq i \leq n
$$

算法：

dp[i][v][d]表示前i件物品（1≤i≤n,0≤v≤V,0≤d≤D）恰好装入容量为v的背包中所能获得的最大价值。

递推：

考虑对i件物品的选择策略:

1、不放第i件物品，那么dp[i][v][d]=dp[i-1][v][d]。

2、放第i件物品，那么问题转化为前i-1件物品恰好装入容量为v-w[i],d-b[i]的背包中所能获得的最大价值，也即dp[i-1][v-w[i]][d-b[i]]+c[i]

$$ dp[i][v][d]=max\left\{dp[i-1][v][d],dp[i-1][v-w[i]][d-b[i]]+c[i]\right\}$$

$$(1\le i \le n ,w[i]\le v\le V,b[i]\le d)$$