完全背包详解

完全背包 一、问题引出

现在一共有 N N N 件物品，第i（i从1开始）件物品的重量为 v [ i ] v[i] v[i] ，价值为 w [ i ] w[i] w[i] 。每个物品可以挑选 无数次 ，且在挑选出来的物品的总重量不超过 V V V 的情况下，能装入背包的物品的总价值和最大为多少

二、分析

现在我们对每一个物品的抉择就不只是 “选” 和 “不选” 了，因为现在每一个物品可以选择无限次，但是我们的背包容量还是有限制的，假设说一个背包全装第 i i i 个物品，那么最多装 K = ⌊ V v [ i ] ⌋ K = \left \lfloor \frac{V}{v[i]} \right \rfloor K=⌊v[i]V​⌋ 这么多个，于是我们将每一个物品的 上限次数 求出来了 那么我们的状态转移方程其实就可以写成这样:

F [ i ] [ j ] = m a x { F [ i − 1 ] [ V − k × v [ i ] ] + k × w [ i ] }   ( 0 < = k × v [ i ] < = V ) F[i][j] = max\{F[i-1][V-k\times v[i]] + k\times w[i]\} \ (0V; int a,b; int cnt = 0; for(int i = 1;i >a>>b; for(int j = 1,l = V/a;j v[i]>>w[i]; for(int i = 1;i = v[i]; --j) for(int k = 1,l = V/v[i]; k = v[i] * k) f[j] = max(f[j],f[j - v[i] * k] + w[i] * k); cout>w[i]; for(int i = 1;i