DP——背包问题

当我们谈论背包问题时，可以想象成一个小朋友要去旅行，但是他只能带一个容量有限的背包。他有一些物品可以选择放入背包，每个物品都有自己的重量和价值。小朋友的目标是在不超过背包容量的情况下，选择物品使得总价值最大化。

01背包问题

在$01$背包问题中，小朋友只能选择每个物品要么完全放入背包，要么完全不放入背包。每个物品都有自己的重量和价值，而背包有一个固定的容量限制。小朋友的目标是选择物品，使得它们的总价值最大化，同时不超过背包的容量限制。

举个例子，小朋友的背包容量是$10$，他有以下物品可供选择：

物品$A$：重量$3$，价值$4$
物品$B$：重量$4$，价值$5$
物品$C$：重量$2$，价值$3$

在这种情况下，小朋友可以选择所有物品，它们的总重量是$9$，总价值是$12$，同时不超过背包的容量限制。

分数背包问题

在分数背包问题中，小朋友可以选择每个物品的一部分放入背包。每个物品都有自己的重量和价值，而背包有一个固定的容量限制。小朋友的目标是选择物品的部分，使得它们的总价值最大化，同时不超过背包的容量限制。

举个例子，小朋友的背包容量是10，他有以下物品可供选择：

物品A：重量3，价值4
物品B：重量10，价值6
物品C：重量2，价值3

在这种情况下，小朋友可以选择物品$A$的全部，物品B的一部分（重量为$5$），以及物品$C$的全部。这样总重量是$10$，总价值是 $4+(5/10)\ast 6+3=10$，同时不超过背包的容量限制。

多重背包问题

在多重背包问题中，每个物品有自己的重量、价值和可用数量。背包有一个固定的容量限制。小朋友的目标是选择物品的数量，使得它们的总价值最大化，同时不超过背包的容量限制和物品的可用数量限制。

举个例子，小朋友的背包容量是10，他有以下物品可供选择：

物品A：重量3，价值4，可用数量2
物品B：重量4，价值5，可用数量1
物品C：重量2，价值3，可用数量3

在这种情况下，小朋友可以选择物品A两个以及物品C两个。这样总重量是(3 2) + (22) = 10，总价值是(4*2) +(3 *2) =14，同时不超过背包的容量限制和物品的可用数量限制。

完全背包问题

在无界背包问题中，每个物品有自己的重量和价值，但是每个物品的数量是无限的。背包有一个固定的容量限制。小朋友的目标是选择物品的数量，使得它们的总价值最大化，同时不超过背包的容量限制。

举个例子，小朋友的背包容量是10，他有以下物品可供选择：

物品A：重量3，价值4
物品B：重量4，价值5
物品C：重量2，价值3

在这种情况下，小朋友可以选择物品C五个。这样总重量是5* 2) = 14，总价值为3*5 = 15，同时不超过背包的容量限制。