描述

有n种物品和一个容积为V的背包，每种物品i都有无限个，都有体积cost[i]和价值valum[i]，问如何选取物品使得放入背包的物品价值之和最大。

思路

完全背包和01背包很像，我们首先想到的应该是每种物品在拿0~n个中选max价值的，我们依旧用dp[i][j]来储存将前i种物品放入体积为j的背包中物品价值之和最大值，那么状态转移方程便是在放得下的情况下 $dp[i][j]=Max\{dp[i-1][j-k \times cost[i] + k \times valum[i]\}$ $(0\leq k \times cost[i] \leq V)$

这样最后求出来的dp[n][V]就是最后答案。

时间复杂度:O($V \times {\sum_{i=1}^N{V \over {c[i]}}}$)，空间复杂度:O(NV)。

优化

在01背包问题里面，我们逆序遍历V$(j:V \to 0)$是为了保证dp[j-cost[i]]始终是i-1物品推出的，从而保证每种物品只用一次。而完全背包问题里面我们就可以正序遍历，这样就可以在一次遍历dp[V]中考虑第i种物品的所有拿法。
核心代码如下:
1
2
3
for(int i=1;i<=n;i++)
      for(int j=cost[i];j<=V;j++)
        dp[j]=max(dp[j],dp[j-cost[i]]+valum[i]);
优化后时间复杂度为O(NV)，空间复杂度为O(N)。

初始化

如果题目没有要求必须装满，那么我们只要将dp数组全部置为0即可。

如果必须装满，我们就将dp[0]初始化为0，其他初始化为$-\infty$。

例题

板子题：洛谷1616