【第二十五课】动态规划：完全背包问题(acwing-3 / 公式推导 / 思路理解 / 优化 / c++代码)

���录

思路

朴素代码

优化

公式推导上 

二维代码 

一维代码

公式理解上

在开始看完全背包问题之前，可能需要先了解01背包及其解决办法。 指路

【第二十五课】动态规划：01背包问题(acwing-2 / 思路 / 含一维数组优化 / c++代码)

思路

这个问题和01背包的区别就是每件物品可以选无限次(当然在背包容量限制之内)。

也就是说，01背包中我们在面对第i件物品的时候，有两种选择，分别是：选和不选，也就是第 i 件物品选择0次和1次，而完全背包也就是说，我们可选择的选项变多了，我们可以选择第i件物品 0，1，2，3，......k次，也就是在01背包分析问题方法的基础上，做了一点变化，如图

如果仅仅是这里发生了改变的话，其实我们在不考虑优化情况下，最朴素的写法应该是很容易得出的。

状态转移方程变为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*v[i]]+k*w[i]) 

都是为了填充这个二维数组，只不过把选择从0和1两个变成了0-k个。

朴素代码

#includeusing namespace std;const int N=1010;int n,m;int v[N],w[N];int dp[N][N];int main(){    cin>>n>>m;    for(int i=1;i>v[i]>>w[i];    for(int i=1;iv[i]>>w[i];    for(int i=1;i>m;    for(int i=1;i>v[i]>>w[i];    for(int i=1;i