01背包问题详解【动态规划】

本文主要是介绍01背包问题详解【动态规划】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

01背包：

假设有 n 件物品，至多可装入容积为 m 的容器当中，试问最大可装入的价值为多少？

设w[ i ]为第 i 件物品重量，v[ i ]为第i件物品价值

dp[ i ][ j ]表示将前i件物品装入重量 j 的容器当中

dp方程：

当 i = 0时，dp[ 0 ][ j ]表示把前0件物品装入j大小的容器，总价值为0，所以dp[ 0 ][ j ] = 0
当 j = 0时，dp[ i ][ 0 ]表示把前i件物品装入0大小的容器，总价值为0，所以dp[ i ][ 0 ] = 0
当 j < w[ i ] 时，第 i 件物品无法装入，dp[ i ][ j ] = dp[ i-1 ][ j ]
当 j >= w[ i ]时，dp[ i ][ j ] = max( dp[ i-1 ][ j ], dp[ i -1 ][ j-w[ i ]] + v[ i ] )

样例输入：

第一行：物品总数n
第二行：最大容量full
第三行：n个物品的重量
第四回：n个物品的价值

5
10
2 2 6 5 4
6 3 5 4 6

样例输出：

最大可装入价值

dp状态表

i \ j	1	2	3	4	5	6	7	8	9	10
0	0	0	0	0	0	0	0	0	0	0
1	0	6	6	6	6	6	6	6	6	6
2	0	6	6	9	9	9	9	9	9	9
3	0	6	6	9	9	9	9	11	11	14
4	0	6	6	9	9	9	10	11	13	14
5	0	6	6	9	12	12	12	15	15	15

代码模板：

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1001//物品最大数 
#define MAXM 1001//重量最大数 
int dp[MAXN][MAXM];//dp数组 
int w[MAXN],v[MAXN];//重量和价值数组 
int n;//物品数量
int full;//最大可装重量 
void solve();//解题函数 
int main(){cin>>n;//输入数量cin>>full;//输入重量  for(int i=1;i<=n;i++){cin>>w[i];//输入重量 }for(int i=1;i<=n;i++){cin>>v[i];//输入价值 }solve(); return 0;
}
void solve(){for(int i=0;i<=n;i++){for(int j=0;j<=full;j++){if(i==0 || j==0) dp[i][j]=0;//边界dp，结果为0 else{if(j<w[i]) dp[i][j]=dp[i-1][j];//装不下 else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//装得下，max比较装或不装哪个更大 }}}cout<<dp[n][full]<<endl;//输出结果 
}

空间优化：

由于算法时间复杂度已经无法优化，但我们可以考虑优化空间复杂度

从上述代码我们可以看出，dp数组每次都是调用前一轮dp的结果，因此可以采用滚动数组来保存决策量

dp方程：

只需要修改dp[ i ][ j ]修改为dp[ i%2 ][ j ]

因此，dp[ i -1 ][ j ]修改为dp[ (i-1)%2 ][ j ]

初始化 i = 0，每轮dp之后 i += 1

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 1001//物品最大数 
#define MAXM 1001//重量最大数 
int dp[2][MAXM];//dp数组 
int w[MAXN],v[MAXN];//重量和价值数组 
int n;//物品数量
int full;//最大可装重量 
void solve();//解题函数 
int main(){cin>>n;//输入数量cin>>full;//输入重量  for(int i=1;i<=n;i++){cin>>w[i];//输入重量 }for(int i=1;i<=n;i++){cin>>v[i];//输入价值 }solve(); return 0;
}
void solve(){for(int i=0;i<=n;i++){for(int j=0;j<=full;j++){if(i==0 || j==0) dp[i%2][j]=0;//边界dp，结果为0 else{if(j<w[i]) dp[i%2][j]=dp[(i-1)%2][j];//装不下 else dp[i%2][j]=max(dp[(i-1)%2][j],dp[(i-1)%2][j-w[i]]+v[i]);//装得下，max比较装或不装哪个更大 }}}cout<<dp[n%2][full]<<endl;//输出结果 
}

这篇关于01背包问题详解【动态规划】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！