【题目链接】ybt 1272【例9.16】分组背包【题目考点】1. 动态规划分组背包【解题思路】分组背包问题特点是每组中的物品最多可以取一件1. 状态定义集合放入背包的物品方案限制物品所在分组的区间背包大小属性价值条件最大统计量价值状态定义dp[i][j]: 在前i组物品中选择物品放入大小为j的背包能获得的最大价值。2. 状态转移方程记第i组物品有m个这m个物品的编号为i1,i2,…,im。第i物品的重量是w[i]价值是c[i]。集合在前i组物品中选择物品放入大小为j的背包的所有方案分割集合第i组物品如何放入背包如果不选择第i组物品那么在剩余i-1组中选择物品放入大小为j的背包。dp[i][j] dp[i-1][j]如果选择第i组物品中的第1个该物品下标为i1。那么需要在剩余i-1组中选择物品放入大小为j-w[i1]的背包。dp[i][j] dp[i-1][j-w[i1]]c[i1]如果选择第i组物品中的第2个该物品下标为i2。那么需要在剩余i-1组中选择物品放入大小为j-w[i2]的背包。dp[i][j] dp[i-1][j-w[i2]]c[i2]…如果选择第i组物品中的第m个该物品下标为im。那么需要在剩余i-1组中选择物品放入大小为j-w[im]的背包。dp[i][j] dp[i-1][j-w[im]]c[im]一般地如果选择第i组物品中的第k个该物品下标为x。那么需要在剩余i-1组中选择物品放入大小为j-w[x]的背包。dp[i][j] dp[i-1][j-w[x]]c[x]。遍历第i组物品求选择该组中每个物品后能得到的最大价值dp[i][j]。以上所有情况求最大值。3. 复杂度分析背包容量为V物品总数量为N分组数量为T。分组背包一般解法时间复杂度O ( V N ) O(VN)O(VN)空间复杂度O ( T V ) O(TV)O(TV)滚动数组优化后空间复杂度O ( V ) O(V)O(V)【题解代码】解法1分组背包 一般解法#includebits/stdc.husingnamespacestd;#defineV205#defineN35#defineT15intdp[T][V],w[N],c[N];//dp[i][j]:在前i组物品中选择物品放入大小为j的背包能获得的最大价值。vectorintg[T];//g[i]:存储第i组物品的编号intmain(){intv,n,t,p;cinvnt;for(inti1;in;i){cinw[i]c[i]p;g[p].push_back(i);//第p组添加i}for(inti1;it;i)//遍历各组{for(intj0;jv;j){dp[i][j]dp[i-1][j];for(intk0;kg[i].size();k){intxg[i][k];if(w[x]j)dp[i][j]max(dp[i][j],dp[i-1][j-w[x]]c[x]);}}}coutdp[t][v];return0;}解法2分组背包 滚动数组优化#includebits/stdc.husingnamespacestd;#defineV205#defineN35#defineT15intdp[V],w[N],c[N];//dp[i][j]:第1维被优化掉在前i组物品中选择物品放入大小为j的背包能获得的最大价值。vectorintg[T];//g[i]:存储第i组物品的编号intmain(){intv,n,t,p;cinvnt;for(inti1;in;i){cinw[i]c[i]p;g[p].push_back(i);//第p组添加i}for(inti1;it;i)//遍历各组{for(intjv;j0;--j){for(intk0;kg[i].size();k){intxg[i][k];if(jw[x])dp[j]max(dp[j],dp[j-w[x]]c[x]);}}}coutdp[v];return0;}
【题目链接】ybt 1272【例9.16】分组背包【题目考点】1. 动态规划分组背包【解题思路】分组背包问题特点是每组中的物品最多可以取一件1. 状态定义集合放入背包的物品方案限制物品所在分组的区间背包大小属性价值条件最大统计量价值状态定义dp[i][j]: 在前i组物品中选择物品放入大小为j的背包能获得的最大价值。2. 状态转移方程记第i组物品有m个这m个物品的编号为i1,i2,…,im。第i物品的重量是w[i]价值是c[i]。集合在前i组物品中选择物品放入大小为j的背包的所有方案分割集合第i组物品如何放入背包如果不选择第i组物品那么在剩余i-1组中选择物品放入大小为j的背包。dp[i][j] dp[i-1][j]如果选择第i组物品中的第1个该物品下标为i1。那么需要在剩余i-1组中选择物品放入大小为j-w[i1]的背包。dp[i][j] dp[i-1][j-w[i1]]c[i1]如果选择第i组物品中的第2个该物品下标为i2。那么需要在剩余i-1组中选择物品放入大小为j-w[i2]的背包。dp[i][j] dp[i-1][j-w[i2]]c[i2]…如果选择第i组物品中的第m个该物品下标为im。那么需要在剩余i-1组中选择物品放入大小为j-w[im]的背包。dp[i][j] dp[i-1][j-w[im]]c[im]一般地如果选择第i组物品中的第k个该物品下标为x。那么需要在剩余i-1组中选择物品放入大小为j-w[x]的背包。dp[i][j] dp[i-1][j-w[x]]c[x]。遍历第i组物品求选择该组中每个物品后能得到的最大价值dp[i][j]。以上所有情况求最大值。3. 复杂度分析背包容量为V物品总数量为N分组数量为T。分组背包一般解法时间复杂度O ( V N ) O(VN)O(VN)空间复杂度O ( T V ) O(TV)O(TV)滚动数组优化后空间复杂度O ( V ) O(V)O(V)【题解代码】解法1分组背包 一般解法#includebits/stdc.husingnamespacestd;#defineV205#defineN35#defineT15intdp[T][V],w[N],c[N];//dp[i][j]:在前i组物品中选择物品放入大小为j的背包能获得的最大价值。vectorintg[T];//g[i]:存储第i组物品的编号intmain(){intv,n,t,p;cinvnt;for(inti1;in;i){cinw[i]c[i]p;g[p].push_back(i);//第p组添加i}for(inti1;it;i)//遍历各组{for(intj0;jv;j){dp[i][j]dp[i-1][j];for(intk0;kg[i].size();k){intxg[i][k];if(w[x]j)dp[i][j]max(dp[i][j],dp[i-1][j-w[x]]c[x]);}}}coutdp[t][v];return0;}解法2分组背包 滚动数组优化#includebits/stdc.husingnamespacestd;#defineV205#defineN35#defineT15intdp[V],w[N],c[N];//dp[i][j]:第1维被优化掉在前i组物品中选择物品放入大小为j的背包能获得的最大价值。vectorintg[T];//g[i]:存储第i组物品的编号intmain(){intv,n,t,p;cinvnt;for(inti1;in;i){cinw[i]c[i]p;g[p].push_back(i);//第p组添加i}for(inti1;it;i)//遍历各组{for(intjv;j0;--j){for(intk0;kg[i].size();k){intxg[i][k];if(jw[x])dp[j]max(dp[j],dp[j-w[x]]c[x]);}}}coutdp[v];return0;}
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
