国内亲子游做的最好的网站,门户网站开发平台,产品发布网站,ios开发教程0/1背包
背包问题是DP最经典的类型之一#xff0c;而0/1背包是最经典最基础的背包问题。
背包体积为 V V V#xff0c; n n n种物品#xff0c;每种物品只有1个#xff0c;第 i i i种物品对应体积为 c i c_i ci#xff0c;价值为 w i w_i wi#xff0c;怎样装填能使…0/1背包
背包问题是DP最经典的类型之一而0/1背包是最经典最基础的背包问题。
背包体积为 V V V n n n种物品每种物品只有1个第 i i i种物品对应体积为 c i c_i ci价值为 w i w_i wi怎样装填能使背包总价值最大
由于每件物品只有选(0)与不选(1)两种情况故称为0/1背包问题。
分析闫氏DP分析法 状态表示 集合定义数组 d p [ i ] [ j ] dp[i][j] dp[i][j]表示当前选取方案的价值。第 i i i行表示只考虑前 i i i个物品的放置情况 j j j表示当前选取体积不超过 j j j的方案集合。属性 M a x Max Max初始化对于最值问题 d p [ i ] [ 0 ] f [ 0 ] [ j ] 0 dp[i][0]f[0][j]0 dp[i][0]f[0][j]0 状态计算 d p [ i ] [ j ] dp[i][j] dp[i][j]对于第 i i i种物品 不可选第 i i i种物品 v c [ i ] vc[i] vc[i]无法装入背包背包剩余容积不变。集合状态仍为 [ 1 , i − 1 ] [1,i-1] [1,i−1]直接继承自第 i − 1 i-1 i−1种物品且背包容积仍为 j j j方案的价值。 d p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j]dp[i-1][j] dp[i][j]dp[i−1][j]可选第 i i i种物品 不选第 i i i种物品若选第 i i i种物品无法保证最优解则不选背包剩余容积不变。集合状态仍为 [ 1 , i − 1 ] [1,i-1] [1,i−1]直接继承自第 i − 1 i-1 i−1个物品且背包容积仍为 j j j方案的价值。 d p [ i ] [ j ] d p [ i − 1 ] [ j ] dp[i][j]dp[i-1][j] dp[i][j]dp[i−1][j]选第 i i i种物品选第 i i i种物品可能导致产生最优解则选。集合状态仍为 [ 1 , i − 1 ] [1,i-1] [1,i−1]因为0/1背包要求每种物品只能选一次故继承自第 i − 1 i-1 i−1种物品且背包容积减少 c [ i ] c[i] c[i]方案的价值并加 w [ i ] w[i] w[i]。 d p [ i ] [ j ] d p [ i − 1 ] [ j − c [ i ] ] w [ i ] dp[i][j]dp[i-1][j-c[i]]w[i] dp[i][j]dp[i−1][j−c[i]]w[i] 状态转移方程式 d p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c [ i ] ] w [ i ] ) dp[i][j]max(dp[i-1][j],dp[i-1][j-c[i]]w[i]) dp[i][j]max(dp[i−1][j],dp[i−1][j−c[i]]w[i])
遍历顺序物品和背包谁先遍历都可以根据状态转移方程式dp数组的当前位置只与正上方和左上方有关无论哪种遍历顺序都可以确保在到达当前位置之前正上方和左上方都有值。
初始化 void init(){for(int i0;in;i) dp[i][0]0;for(int i0;iv;i) dp[0][j]0;
}
void dp(){for(int i1;in;i)//遍历物品for(int j1;jv;j)//遍历背包if(c[i]j) dp[i][j]max(dp[i-1][j],dp[i-1][j-c[i]]w[i]);else dp[i][j]dp[i-1][j];
}时间复杂度O( n v nv nv)空间复杂度O( n v nv nv)
DP表 滚动数组
DP问题的空间复杂度一般很高可采用滚动数组方式对空间复杂度进行优化。
滚动数组原理是基于DP的无后效性第 i i i行只与 i − 1 i-1 i−1行有关至于 i − 1 i-1 i−1行之前的数据第 i i i行无需关注因此在DP过程中实际上只有两行在进行工作故可极大程度优化空间复杂度。
注意滚动数组使中间信息丢失若需要输出背包具体方案则不能采用滚动数组。
交替滚动
思路定义 d p [ 2 ] [ v ] dp[2][v] dp[2][v]当前工作指针 w o r k work work和上次工作指针 o l d old old使用 d p [ w o r k ] [ v ] dp[work][v] dp[work][v]和 d p [ o l d ] [ v ] dp[old][v] dp[old][v]进行交替滚动每次滚动后交换工作指针即可思路简单
int dp[2][v];
void dp(){int work0,old1;for(int i1;in;i){swap(work,old);//交换工作指针而非交换数组元素for(int j1;jv;j)if(c[i]j) dp[work][j]max(dp[old][j],dp[old][j-c[i]]w[i]);else dp[work][j]dp[old][j];}
}自我滚动
思路由状态转移方程式可知当前元素只继承自上一行正上方( d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j])或上一行左上方( d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i−1][j−1])因此逆序遍历背包容量进行更新可将数组压至一维。
必须对背包进行逆序更新这样是为了满足0/1背包每种物品只能选1个的性质若顺序遍历则可能会对1种物品选多次此时则为完全背包且此错误必然会在选第1种物品时就发生。
自我滚动的0/1背包只可先遍历物品再遍历背包不可颠倒(完全背包可颠倒)。 int dp[v];
void dp(){for(int i1;in;i){//顺序遍历物品for(int jv;jc[i];j--)//逆序遍历背包,装不下的不用管dp[j]max(dp[j],dp[j-c[i]]w[i]);}
}输出具体方案
思路定义标记数组从 d p dp dp终点开始步步向上回溯根据0/1背包状态转移方程式 p [ i ] [ j ] m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c [ i ] ] w [ i ] ) p[i][j]max(dp[i-1][j],dp[i-1][j-c[i]]w[i]) p[i][j]max(dp[i−1][j],dp[i−1][j−c[i]]w[i])可知判断 d p [ i ] [ j ] dp[i][j] dp[i][j]与 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]和 d p [ i − 1 ] [ j − c [ i ] ] w [ i ] dp[i-1][j-c[i]]w[i] dp[i−1][j−c[i]]w[i]关系即可判断第 i i i个物品是否已装最后输出标记数组。
注求解具体方案仅适用于非滚动数组因为滚动过程会将中间状态信息丢失。
extern int dp[MAX][MAX],i,j;//i,j:dp终点
bool f[MAX];
void print(){for(;i1;i--){if(jc[i]dp[i][j]dp[i-1][j-c[i]w[i]]){//说明第i个物品已选f[i]1;j-c[i];}}for(int k1;kn;k) if(f[k]) coutk ;
}
