阜蒙县自治区建设学校网站,美图秀秀网页版入口,.asp 网站,wordpress 写作工具目录
1. 朴素解法
2. 优化 原题链接#xff1a; 3. 完全背包问题 - AcWing题库 题目描述#xff1a; 有 N 种物品和一个容量是 V 的背包#xff0c;每种物品都有无限件可用。 第 i 种物品的体积是 vi#xff0c;价值是 wi。 求解将哪些物品装入背包#xff0c;可使这些…目录
1. 朴素解法
2. 优化 原题链接 3. 完全背包问题 - AcWing题库 题目描述 有 N 种物品和一个容量是 V 的背包每种物品都有无限件可用。 第 i 种物品的体积是 vi价值是 wi。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 输入格式 第一行两个整数NV用空格隔开分别表示物品种数和背包容积。 接下来有 N 行每行两个整数 vi, wi用空格隔开分别表示第 i 种物品的体积和价值。 输出格式 输出一个整数表示最大价值。 数据范围 0 N, V ≤10000 0 vi, wi ≤ 1000 输入样例 4 5
1 2
2 4
3 4
4 5输出样例 10 在解决这道题之前我们先来回顾一下 Acwing 的讲师y总他讲述的解决动态规划问题的一般步骤 。 集合表示状态中每一个下标位置可能的选择。一维数组也好二维数组也罢动态规划处理之后里面存储的元素就是这个状态下对应的最终结果。而这个结果的产生就是集合中满足题意的那个元素。 属性属性需要根据题意来选择。就拿本题来说要计算价值的最大值那么属性就是集合中价值的最大值 状态计算将每一个状态中的集合进行划分根据集合的划分推出状态转移方程。 集合划分的依据划分出来的所有集合的并集不得遗漏一个状态中的任何选择。但是可以重复。 1. 朴素解法
这道题的状态表示和 01 背包问题里面的状态表示相同。
状态表示中的集合从 1 - i 个物品中选并且物品的总体积不超过 j 的所有选法
状态表示中的属性集合中所有选法的价值最大值。 我想你现在对 集合 与 属性的关系一定有了自己的理解动态规划存储结果的数组中的一个元素都是该状态下的集合中满足一定属性的那个值 下面我们来看状态计算我们在 01 背包问题中将集合划分成了是否选择第 i 个物品两个部分。我们可以借鉴 01 背包问题的思路。 完全背包问题中我们将集合划分为 第 i 个物品选择 0 个 第 i 个物品选择 1 个 第 i 个物品选择 2 个 ······ 第 i 个物品选择 k 个 若干个部分。 根据上图我们将集合划分成了若干部分并且如此划分集合满足集合划分的依据下一步要做的就是推导出状态转移方程即如何计算出集合中价值的最大值。
同时我们还注意到 k 不能胡乱取值因为我们的背包体积是有限的当 k * v[i] 大于 背包的体积此时往后的 k 都是无效的。
下面我们来推导状态转移方程
我们不妨假设第 i 个物品我们选择了 k 个。
当 k 0 时说明不选择第 i 个物品此时 f [i, j] f [i - 1, j]这倒是很简单
当 k 不等于 0 时该怎么办呢同样借鉴一下 01 背包问题的想法之前假设第 i 个物品选择了 k 个我们可以先不看第 i 个物品那么问题就变成了从 1 - (i - 1) 中的物品中做选择但是选择的体积还是不大于 j 吗当然不是因为我们忽略了第 i 个物品并且我们选择了 k 个第 i 个物品因此选择的总体积应该是不大于 j - k * v[i](v[i] 是第 i 个物品的体积)。
那么当 k 不等于 0 时状态转移方程就可以写成f [i, j] f [ i - 1][ j - k * v[i] ] k * w[i]。这里为什么要加上 k * w[i] 呢因为 f [ i - 1][ j - k * v[i] ] 是忽略了第 i 个物品的选择的价值最大值想要计算 f [ i, j ] 肯定要算上第 i 个物品的选择嘛
最后我们惊奇的发现k 0 与 k ! 0f [i, j] 都等于 f [ i - 1][ j - k * v[i] ] k * w[i]。
因为要求的是价值的最大值因此在遍历 k 的取值时要取价值最大的那一个
#includeiostream
#includealgorithm
using namespace std;const int N 1010;
int v[N], w[N];
int f[N][N];
int n, m;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 0; 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;
}
2. 优化
优化的味道有点向数学我们需要将 f[i, j] 的状态转移方程展开 我们发现灰色的那一坨是差不多的就差了一个 w[i]因此我们的状态转移方程可以修改为
f[i, j] max( f[i - 1][j] f[i, j - v[i]] w[i] )
#includeiostream
#includealgorithm
using namespace std;const int N 1010;
int v[N], w[N];
int f[N][N];
int n, m;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 0; j m; j){f[i][j] f[i - 1][j];if(j v[i])f[i][j] max(f[i][j], f[i][j - v[i]] w[i]);}}cout f[n][m] endl;return 0;
}
再根据 01 背包问题的空间优化完全背包问题的空间也是可以优化到一维的并且根据状态转移方程从小到大枚举并无问题因为 j - v[i] 一定在之前被计算过因此完全背包问题的最终代码
#includeiostream
#includealgorithm
using namespace std;const int N 1010;
int v[N], w[N];
int f[N];
int n, m;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 v[i]; j m; j)f[j] max(f[j], f[j - v[i]] w[i]);cout f[m] endl;return 0;
}
