门户网站 意义,郑州最好的品牌策划公司,建站公司排名前十名,百度收录不到公司网站文章目录 一、0-1背包概述1.1 问题描述1.2 算法思想 二、0-1背包代码2.1 题目描述2.2 代码编写 三、完全背包概述四、完全背包代码4.1 题目描述4.1 代码编写4.2 代码优化 一、0-1背包概述
1.1 问题描述 1. 0-1背包问题#xff1a;给定 n n n 种物品和一背包。物品 i i i 的… 文章目录 一、0-1背包概述1.1 问题描述1.2 算法思想 二、0-1背包代码2.1 题目描述2.2 代码编写 三、完全背包概述四、完全背包代码4.1 题目描述4.1 代码编写4.2 代码优化 一、0-1背包概述
1.1 问题描述 1. 0-1背包问题给定 n n n 种物品和一背包。物品 i i i 的体积是 v i v_i vi其价值为 w i w_i wi背包的容量为 c c c。问应如何选择装入背包的物品使得装入背包中物品的总价值最大? 2. 在选择装入背包的物品时对每种物品 i i i 只有两种选择即装入背包和不装入背包。不能将物品 i i i 装入背包多次也不能只装入部分的物品 i i i。
1.2 算法思想 1. f [ i ] [ j ] f[i][j] f[i][j] 定义前 i i i 个物品背包容量 j j j 下的最优解最大价值。
当前的状态依赖于之前的状态可以理解为从初始状态 f [ 0 ] [ 0 ] 0 f[0][0] 0 f[0][0]0 开始决策有 n n n 件物品则需要 n n n 次决策。每一次对第 i i i 件物品的决策状态 f [ i ] [ j ] f[i][j] f[i][j] 不断由之前的状态更新而来。 2. 当前背包容量不够 j v [ i ] j v[i] jv[i]没得选因此前 i i i 个物品最优解即为前 i − 1 i−1 i−1 个物品最优解。
对应代码f[i][j] f[i - 1][j]。 3. 当前背包容量够 j v [ i ] j v[i] jv[i]可以选因此需要决策选与不选第 i i i 个物品。
选f[i][j] f[i - 1][j - v[i]] w[i]。不选f[i][j] f[i - 1][j]。我们的决策是如何取到最大价值因此以上两种情况取 max() 。
二、0-1背包代码
2.1 题目描述 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例 8 2.2 代码编写 #includebits/stdc.h
using namespace std;const int MAXN 1005;
int v[MAXN]; // 体积
int w[MAXN]; // 价值
int f[MAXN][MAXN]; // f[i][j], j体积下前i个物品的最大价值 int main()
{int n, m; //n表示物品的数量m表示背包容积 cin n m;for(int i 1; i n; i) cin v[i] w[i]; //从1开始输入每个物品的体积和价值for(int i 0; i m; i) //设置在没有物品情况下无论背包有多少体积价值都为0f[0][i]0;for(int j 0; j n; j) //设置在背包体积为0情况下无论有多少物品价值都为0f[j][0]0;for(int i 1; i n; i) for(int j 1; j m; j){// 当前背包容量装不进第i个物品则价值等于前i-1个物品if(j v[i]) f[i][j] f[i - 1][j];// 能装需进行决策是否选择第i个物品else f[i][j] max(f[i - 1][j], f[i - 1][j - v[i]] w[i]);} cout f[n][m] endl;return 0;
}三、完全背包概述 1. 思路同0-1背包问题。区别在于0-1背包对于每种物品只有选或不选这也0-1的由来。而完全背包则对于每种物品可以多次选择。 2. 因为选择物品的总体积不能超过 j j j 所以第 i i i 件物品最多选 j / v i j / v_i j/vi向下取整件。 3. f [ i ] [ j ] f[i][j] f[i][j] 定义前 i i i 个物品背包容量 j j j 下的最优解最大价值。 f [ i ] [ j ] m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v i ] w i , f [ i − 1 ] [ j − 2 ∗ v i ] 2 ∗ w i , f [ i − 1 ] [ j − k ∗ v i ] k ∗ w i , . . . . . ) f[i] [j] max( f[i-1][j] , f[i - 1][j - v_i]w_i , f[i - 1][j - 2 * v_i] 2 * w_i , f[i - 1][j - k * v_i ] k * w_i , .....) f[i][j]max(f[i−1][j],f[i−1][j−vi]wi,f[i−1][j−2∗vi]2∗wi,f[i−1][j−k∗vi]k∗wi,.....)。
四、完全背包代码
4.1 题目描述 输入样例 4 5 1 2 2 4 3 4 4 5 输出样例 10 4.1 代码编写
#includeiostream
using namespace std;const int N 1010;int n, m;
int f[N][N]{0}, v[N], w[N];int main(){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 )for(int k 0; k * v[i] j; k )f[i][j] max(f[i][j], f[i - 1][j - k * v[i]] k * w[i]);cout f[n][m] endl;return 0;
}4.2 代码优化 1. f [ i ] [ j ] m a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v i ] w i , f [ i − 1 ] [ j − 2 ∗ v i ] 2 ∗ w i , f [ i − 1 ] [ j − k ∗ v i ] k ∗ w i , . . . . . ) f[i] [j] max( f[i-1][j] , f[i - 1][j - v_i]w_i , f[i - 1][j - 2 * v_i] 2 * w_i , f[i - 1][j - k * v_i ] k * w_i , .....) f[i][j]max(f[i−1][j],f[i−1][j−vi]wi,f[i−1][j−2∗vi]2∗wi,f[i−1][j−k∗vi]k∗wi,.....)。 f [ i ] [ j − v i ] m a x ( f [ i − 1 ] [ j − v i ] , f [ i − 1 ] [ j − 2 ∗ v i ] w i , f [ i − 1 ] [ j − 3 ∗ v i ] 2 ∗ w i , . . . . . ) f[i][j - v_i] max( f[i-1][j - v_i] , f[i-1][j - 2 * v_i] w_i , f[i-1][j - 3 * v_i] 2 * w_i , .....) f[i][j−vi]max(f[i−1][j−vi],f[i−1][j−2∗vi]wi,f[i−1][j−3∗vi]2∗wi,.....) 。 由上面的两式可得出如下递推关系f[i][j] max(f[i][j-v[i]] w[i] , f[i-1][j])。 2. 去掉第三层的 k k k 循环优化后的代码如下
#includeiostream
using namespace std;const int N 1010;int n, m;
int f[N][N]{0}, v[N], w[N];int main()
{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(v[i] j)f[i][j] max(f[i - 1][j], f[i][j - v[i]] w[i]);elsef[i][j] f[i - 1][j];}}cout f[n][m] endl;return 0;
}
