与01不同的是，容量有限而数量无限，那么在选择第i个之后，还可以选择第i个物品，转移方程如下
不选第i件物品，那么和01背包问题一样dp[i][v] = dp[i - 1][v]
选第i件，由于选完以后还可以选（或者说选之前不必是i-1的状态）dp[i][v] = dp[i][v - w[i]] + c[i]
二维形式:dp[i][v] = max(dp[i - 1][v], dp[i][v - w[i]] + c[i])
一维形式(与01背包问题的一致)dp[v] = max(dp[v], dp[v - w[i]] + c[i])
但是，必须从正向枚举，因为dp[i - 1][v] 在dp[i][v]的左边，可以直接覆盖
突然想通了01背包问题的形式为啥是逆向枚举了，因为实际上二维形式是这样的dp[i][v] = max(dp[i - 1][v], dp[i - 1][v - w[i]] + c[i])
这个时候的
若有收获，就点个赞吧
0 人点赞
