南头专业企业网站建设公司,北京的招聘网站有哪些,广西灵山县建设局网站,合作市建设局网站题目描述 原题链接#xff1a;2. 01背包问题
解题思路
#xff08;1#xff09;二维dp数组
动态规划五步曲#xff1a;
#xff08;1#xff09;dp[i][j]的含义#xff1a; 容量为j时#xff0c;从物品1-物品i中取物品#xff0c;可达到的最大价值
#xff08;2…题目描述 原题链接2. 01背包问题
解题思路
1二维dp数组
动态规划五步曲
1dp[i][j]的含义 容量为j时从物品1-物品i中取物品可达到的最大价值
2递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i])其中dp[i - 1][j]表示不放物品i时的最大价值j - v[i]表示给物品i留出空间dp[i - 1][j - v[i]]表示给物品i留出空间后放入其余物品可达到的最大价值由于是按物品递增顺序遍历因此为从1-i-1的物品dp[i - 1][j - v[i]] w[i]表示放入物品i和其余放入其余物品可到达的最大价值。
3dp数组初始化 dp[0][j] d[i][0] 0, dp[0][j]中j v[i]的取w[i]
4遍历顺序 从小到大先背包后物品或先物品后背包都可以。
5举例 省略
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1010;
int dp[N][N];int main(){int n, m;int v[N], w[N];cin n m;for(int i 1; i n; i) cin v[i] w[i];for(int i 1; i n; i) {for(int j 1; j m; j) {// 当前物品重量大于背包容量时不放该物品if(j v[i]) dp[i][j] dp[i - 1][j];// 当前物品重量小于等于背包容量时在放该物品后和不放该物品之间选择一个最大价值else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]);}}cout dp[n][m] endl;return 0;
}2优化为一维dp数组滚动数组 滚动数组含义本轮所计算的数需要用到上一轮的结果依次类推滚动计算。 优化成一维那就要在遍历上实现与二维相同的逻辑顺序从而实现仅用一维就可以代替二维。
动态规划五步曲
1dp[j]数组的含义 容量为j时装入的物品可达到的最大价值。
2递推公式 dp[j] max(dp[j], dp[j - v[i]])
3dp数组初始化 dp[0] 0
4遍历顺序 两层for循环先遍历物品再遍历背包内层按背包从大到小递减顺序遍历。 如果删除dp中的维度[i]后还保持对j的从小到大遍历那么此时的代码其实是等价于dp[i][j] max(dp[i][j - 1], dp[i][j - v[i])在一遍后续遍历中因为j是从小到大与v[i]相减在后续相减时可能会出现本轮遍历中用过的数会使之前使用过的数重复相加。
而如果以对j进行从大到小遍历因为此时是j是从m到v[i]以此顺序计算dp[j - v[i]]时在一遍后续遍历中都是会基于上一轮对i的遍历而进行判定并且由于j变化而v[i]不变在后续不会出现使用过的数重复相加。每次遍历到的j所对应dp[j - v[i]]都还没有被更新就相当于是之前的状态dp[i - 1][j - v[i]]从而得到dp[j] dp[j - v[i]]就等价于dp[i][j] dp[i - 1][j - v[i]]。
#include iostream
#include cstring
#include algorithmusing namespace std;const int N 1010;
int dp[N];int main(){int n, m;int v[N], w[N];cin n m;for(int i 1; i n; i) cin v[i] w[i];for(int i 1; i n; i) {// 从后向前遍历表示装入一个物品后剩余的可装入容量达到的最大价值for(int j m; j v[i]; j--) {dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout dp[m] endl;return 0;
}参考文章AcWing 2. 01背包问题状态转移方程讲解 、AcWing 2. 01背包问题 、动态规划关于01背包问题你该了解这些滚动数组
