动态规划——完全背包问题

问题描述

完全背包问题就是在i个物品中，i个物品无限多，每个物品的价值为w[i]，背包的容量为V,在不超过最大容量的前提下，选出的价值最大。

解决

我们这么想，从i个物品中选取体积不超过j的最大值。那么，第i个物品可以有很多种选法——0，1，2，3，4，5，k。但要保证k个i物品不能超过j。 这样我们就可以得到一个状态方程f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w........) 我们写一下i个物品,体积不超过j-v的最大值的状态方程，f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2w]+w,.......) 我们发现红色位置它们就相差一个w。 所以对该状态方程进行转换，f[i][j]=max(f[i-1][j],f[i][j-v]+w) 但是现在还是二维的，现在我们对他进行一维的转换f[j]=max(f[j],f[j-v]+w)

image.png

括号里面的f[j],上一层的，f[j-v]上一层的。

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3q8qvva2m6ic