刷赞网站推广软件,代理网课,兰州工程建设信息网站,wap网站开发实例目录
牛客DP41 【模板】01背包
问题一解析
问题二解析
解析代码
滚动数组优化代码 牛客DP41 【模板】01背包
【模板】01背包_牛客题霸_牛客网 #include iostream
using namespace std;int main() {int a, b;while (cin a b) { // 注意 while 处…目录
牛客DP41 【模板】01背包
问题一解析
问题二解析
解析代码
滚动数组优化代码 牛客DP41 【模板】01背包
【模板】01背包_牛客题霸_牛客网 #include iostream
using namespace std;int main() {int a, b;while (cin a b) { // 注意 while 处理多个 casecout a b endl;}
}
// 64 位输出请用 printf(%lld) 问题一解析
背包问题的状态表示非常经典如果不知道怎么来的可以先把它当成一个模板。
以某个位置为结尾结合题目要求定义一个状态表示
dp[i][j] 表示从前 i 个物品中挑选总体积不超过 j 所有的选法中能挑选出来的最大价值。
状态转移方程
线性 dp 状态转移方程分析方式一般都是根据最后一步的状况来分情况讨论
不选第 i 个物品相当于就是去前 i - 1 个物品中挑选并且总体积不超过 j 。此时 dp[i][j] dp[i - 1][j] ;。选择第 i 个物品那么就只能去前 i - 1 个物品中挑选总体积不超过 j - v[i] 的物品。此时 dp[i][j] dp[i - 1][j - v[i]] w[i] ; 。但是这种状态不一定存在要判断 j v[i]。
综上状态转移方程为 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]) ; 初始化、填表顺序、返回值 多加一行方便初始化此时仅需将第一行初始化为 0 即可。因为什么也不选也能满足体积不小于 j 的情况此时的价值为 0 。填表顺序从左往右最后返回dp[n][V] ; 问题二解析 第二问仅需微调一下 dp 过程的五步即可。 因为有可能凑不齐 j 体积的物品因此把不合法的状态设置为 -1 。
以某个位置为结尾结合题目要求定义一个状态表示
dp[i][j] 表示从前 i 个物品中挑选总体积正好等于 j 所有的选法中能挑选出来的最大价值。
状态转移方程
线性 dp 状态转移方程分析方式一般都是根据最后一步的状况来分情况讨论
不选第 i 个物品相当于就是去前 i - 1 个物品中挑选并且总体积不超过 j 。此时 dp[i][j] dp[i - 1][j] ;。选择第 i 个物品那么就只能去前 i - 1 个物品中挑选总体积不超过 j - v[i] 的物品。此时 dp[i][j] dp[i - 1][j - v[i]] w[i] ; 。但是这种状态不一定存在不仅要判断 j v[i] 还要判断 dp[i - 1][j - v[i]] 表示的情况是否存在也就是 dp[i - 1][j - v[i]] ! -1 。
综上状态转移方程为 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]) ; 初始化、填表顺序、返回值 多加一行方便初始化第一行第一个格子为 0 因为正好能凑齐体积为 0 的背包但是第一行第一个格子后面都是 -1 因为没有物品无法满足体积大于 0 的情况。第一列全为0。
填表顺序从左往右最后返回dp[n][V] ; 解析代码
#include iostream
#include cstringusing namespace std;const int N 1010; // OJ定义成全局方便且空间不会轻易溢出
int n, V, v[N], w[N];
int dp[N][N];int main()
{cin n V;for (int i 1; i n; i) // 从1开始读数据{cin v[i] w[i];}for(int i 1; i n; i){for(int j 0; j V; j){dp[i][j] dp[i - 1][j];if(j v[i])dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]);}}cout dp[n][V] endl;memset(dp, 0, sizeof(dp));for(int j 1; j V; j){dp[0][j] -1;}for(int i 1; i n; i){for(int j 0; j V; j){dp[i][j] dp[i - 1][j];if(j v[i] dp[i - 1][j - v[i]] ! -1)dp[i][j] max(dp[i - 1][j], dp[i - 1][j - v[i]] w[i]);}}cout (dp[n][V] -1 ? 0 : dp[n][V]) endl;return 0;
} 滚动数组优化代码
背包问题基本上都是利用滚动数组来做空间上的优化时间也有常数的优化
利用滚动数组优化。直接在原始代码上修改。 第i行元素只依赖于第i-1行元素。理论上只需要保持两行元素所以只需两个数组交替滚动就能完成dp数组的填充。因此空间复杂度从ON^2 变为ON。 这里还可以直接用一个数组来进行优化从前往后去更新数组dp[j - v[ i ]]肯定不比dp[ j ]的值大而改了前面后面的更新就会用到前面更新的数据而本来应该使用原二维数组 i - 1行的数据也就是更新数据之前的因此可以巧妙地从后往前遍历这样就可以避免用到更新后的数据。
在01背包问题中优化的结果为
删掉所有的横坐标。修改一下 j 的遍历顺序。
滚动数组优化代码只需能在原代码上修改就行不用考虑什么状态表示
#include iostream
#include cstringusing namespace std;const int N 1010; // OJ定义成全局方便且空间不会轻易溢出
int n, V, v[N], w[N];
// int dp[N][N];
int dp[N]; // 滚动数组优化把所有dp表左边一维坐标删掉修改遍历顺序int main()
{cin n V;for (int i 1; i n; i) // 从1开始读数据{cin v[i] w[i];}for(int i 1; i n; i){for(int j V; j v[i]; --j) // 滚动数组优化{dp[j] dp[j];dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout dp[V] endl;memset(dp, 0, sizeof(dp));for(int j 1; j V; j){dp[j] -1;}for(int i 1; i n; i){for(int j V; j v[i]; --j) // 滚动数组优化{if(dp[j - v[i]] ! -1)dp[j] max(dp[j], dp[j - v[i]] w[i]);}}cout (dp[V] -1 ? 0 : dp[V]) endl;return 0;
}
