0/1背包

背包问题是DP最经典的类型之一，而0/1背包是最经典最基础的背包问题。

一个背包体积为$v$，现有$n$种物品，第$i$个物品对应体积为$c_i$，价值为$w_i$，每件物品最多可放1次，求解怎样放置能使背包总价值最大？

由于每件物品只有选(0)与不选(1)两种情况，故称为0/1背包问题。

分析：闫氏DP分析法

• 状态表示

  • 集合：定义数组$dp[i][j]$，表示当前选取方案的价值。第$i$行表示只考虑前$i$个物品的放置情况，$j$表示当前选取体积不超过$j$的方案集合。$init(dp[0][i],dp[j][0])=0$
  • 属性：$Max$

• 状态计算

  • $dp[i][j]$：对于第$i$个物品：
    • 选第$i$个物品：$dp[i][j]=dp[i-1][j-c[i]]+w[i]$，继承自前$i-1$个物品的价值，体积减少$c[i]$，价值加$w[i]$
    • 不选第$i$个物品：第$i$个物品$c[i]>j$，无法装入背包；或不选该物品。$dp[i][j]=dp[i-1][j]$，继承自前$i-1$个物品的价值，体积和价值不变

• 状态转移方程式：$dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])$

void init(){
    for(int i=0;i<=n;i++) dp[i][0]=0;
    for(int i=0;i<=v;i++) dp[0][j]=0;
}
void dp(){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=v;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($nv$)，空间复杂度O($nv$)

DP表

滚动数组

DP问题的空间复杂度一般很高，可采用滚动数组方式对空间复杂度进行优化。

滚动数组原理是基于DP的无后效性，第$i$行只与$i-1$行有关，至于$i-1$行之前的数据第$i$行无需关注，因此在DP过程中实际上只有两行在进行工作，故可极大程度优化空间复杂度。

注意，滚动数组使中间信息丢失，若需要输出背包具体方案，则不能采用滚动数组。

交替滚动

思路：定义$dp[2][v]$，当前工作指针$work$和上次工作指针$old$，使用$dp[work][v]$和$dp[old][v]$进行交替滚动，每次滚动后交换工作指针即可，思路简单

int dp[2][v];
void dp(){
    int work=0,old=1;
    for(int i=1;i<=n;i++){
        swap(work,old);//交换工作指针而非交换数组元素
        for(int j=1;j<=v;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];
    }
}

自我滚动

思路：由状态转移方程式可知，当前元素只继承自上一行正上方($dp[i-1][j]$)或上一行左上方($dp[i-1][j-1]$)，因此逆序遍历背包容量进行更新，可将数组压至一维。

int dp[v];
void dp(){
    for(int i=1;i<=n;i++){
        for(int j=v;j>=c[i];j--)//装不下的不用管
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
    }
}

输出具体方案

思路：定义标记数组，从$dp$终点开始步步向上回溯，根据0/1背包状态转移方程式$p[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])$可知，判断$dp[i][j]$与$dp[i-1][j]$和$dp[i-1][j-c[i]]+w[i]$关系即可判断第$i$个物品是否已装，最后输出标记数组。

注：求解具体方案仅适用于非滚动数组，因为滚动过程会将中间状态信息丢失。

extern int dp[MAX][MAX],i,j;//i,j:dp终点
bool f[MAX];
void print(){
    for(;i>=1;i--){
        if(j>=c[i]&&dp[i][j]==dp[i-1][j-c[i]+w[i]]){//说明第i个物品已选
            f[i]=1;
            j-=c[i];
        }
    }
    for(int k=1;k<=n;k++) if(f[k]) cout<<k<<' ';
}