动态规划：完全背包及优化

vlambda
2020-06-07

动态规划：完全背包及优化

Date | 2020.06.05

Topic | 动态规划：完全背包问题及优化

Mood | 被推锅的一天

大大大大大噶好

还是我还是我动态规划：完全背包及优化

今日被Dragon那个家伙推锅了

我把聊天截图放出来

大家来讨伐一下他动态规划：完全背包及优化

滑动查看更多

大家来评评理

他是不是很过分（￣へ￣）

动态规划：完全背包及优化

吐槽归吐槽

今天的干货送给大家~

动态规划：完全背包及优化

问题分析：

其实完全背包问题和0-1背包问题的区别就在于：完全背包的是可以把物品重复放进背包的，个数不限；而0-1背包问题中，每种物品只能装一次。为了给大家更好的呈现它们的区别，我们给大家介绍动态规划的概念。

动态规划：

动态规划是指把一个问题分成若干个子问题，在求解子问题的时候，求解出子问题的最优解，从而得到整个问题的最优解。这便是我对动态规划的理解。既然说是动态的，说明它的状态是不断变化的，专业术语就是：状态一直在转移。

状态转移方程：

状态转移说白了就是比较两个状态，把最优的状态赋值给当前的状态。下面给大家看看两个背包问题的状态转移方程：

0-1背包问题：dp[ i ][ j]=max(dp[ i-1 ][ j ],dp[ i-1 ][ j-weight[ i ]]+value[ i ])

完全背包问题：dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*weight[i]]+k*value[i])（k*weight[i]<=j）

对比两个状态转移方程可以发现：完全背包问题只不过是多了一个参数k，这个参数 k 就是表明这件物品可以重复放进背包。但是必须要注意 k*weight[i]<=j 这个条件。

代码实现：

明白了两种背包的区别，只需要把代码带入就可以了：

#include <bits/stdc++.h>using namespace std;
int main(){ int weight[4]={0,1,2,3}; int value[4]={0,2,3,4}; int dp[4][7]={0}; int N=3,W=6,i,j,k; for(i=1;i<=N;i++) { for(j=1;j<=W;j++) {          for(k=1;k*weight[i]<=j;k++){     dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*weight[i]]+k*value[i]); } } } cout<<dp[N][W]<<endl; return 0;}

算法优化：

直接上代码：

既然说0-1背包问题有优化的方法，那么，完全背包问题有没有呢？直接上代码：

#include <bits/stdc++.h>using namespace std;
int main(){ int weight[4]={0,1,2,3}; int value[4]={0,2,3,4}; int dp[7]={0}; int N=3,W=6,i,j,k; for(i=1;i<=N;i++) {       for(j=1;j<=W;j++)     //注意循环的方向 { for(k=1;k*weight[i]<=j;k++){ dp[j]=max(dp[j],dp[j-k*weight[i]]+k*value[i]); } } } cout<<dp[W]<<endl; return 0;}