动态规划-背包问题

Word count: 1kReading time: 4 min

 2024/04/26 

一、0-1背包问题

1.1 适用场景

0-1背包问题属于背包问题中的一种，其特点是：每个物品只能被选择一次，两种状态即要么装入背包，要么不装入背包。

1.2 问题描述

有一个背包，其容量为m

现有n个物品，每个物品的重量为w[i]，价值为v[i]

现在需要选择一些物品装入背包，使得背包中物品的总价值最大。

1.3 通用代码思路

1.3.1 二维数组方式

数组含义

dp[i][j]表示前i个物品在背包容量为j时的最大价值

状态转移方程

当j<w[i]时，即当前物品的重量大于背包容量，此时无法装入背包，因此dp[i][j]=dp[i-1][j]
当j>=w[i]时，即当前物品的重量小于等于背包容量，此时可以选择装入或者不装入背包，因此dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

通用代码

1. 初始化

通常初始化第一排

2. 遍历顺序

可以采用先物品后背包

也可以采用先背包后物品

3. 背包的遍历顺序

正序就行


for(int i = 1; i < n; ++i){//物品
    for(int j = 0; j <= m; ++j){//背包
        if(j < w[i]) dp[i][j] = dp[i-1][j];
        else dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
}

1.3.2 一维数组方式

数组含义

dp[j]表示背包容量为j时的最大价值

状态转移方程

当j>=w[i]时，即当前物品的重量小于等于背包容量，此时可以选择装入或者不装入背包，因此dp[j]=max(dp[j],dp[j-w[i]]+v[i])

通用代码

1. 初始化

可以不用初始化（全初始化为0）

2. 遍历顺序

必须采用先物品后背包的遍历顺序

3. 背包的遍历顺序

由于要求每个物品只能被选择一次，且状态转移方程是由前面的状态推导出来的

因此背包的遍历顺序必须是逆序的，即从大到小遍历，否则会出现重复选择的情况

for(int i = 0; i < n; ++i){//物品
    for(int j = m; j >= w[i]; --j){//背包
        dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
    }
}

二、完全背包问题

2.1 适用场景

完全背包问题的特点是：每个物品可以被选择多次，两种状态即装入背包或者不装入背包

2.2 问题描述

有一个背包，其容量为m

现有n个物品，每个物品的重量为w[i]，价值为v[i]

现在需要选择一些可重复的物品装入背包，使得背包中物品的总价值最大。

2.3 通用代码思路-一维数组方式

2.3.1 数组含义

dp[j]表示背包容量为j时的最大价值

2.3.2 状态转移方程

当j>=w[i]时，即当前物品的重量小于等于背包容量，此时可以选择装入或者不装入背包，因此dp[j]=max(dp[j],dp[j-w[i]]+v[i])

2.3.3 通用代码

1. 初始化

可以不用初始化（全初始化为0）

2. 遍历顺序

可以采用先物品后背包

也可以采用先背包后物品

3. 背包的遍历顺序

由于要求每个物品可以被选择多次，所以允许前面的状态中也包含该物品

因此背包的遍历顺序必须是正序的，即从小到大遍历

先遍历物品，再遍历背包

for(int i = 0; i < n; ++i){//物品
    for(int j = w[i]; j <= m; ++j){//背包
        dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
    }
}

先遍历背包，再遍历物品

for(int j = w[i]; j <= m; ++j){//背包
    for(int i = 0; i < n; ++i){//物品
        dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
    }
}

Author：AkiraZheng

Link：https://akirazheng.github.io/2024/04/26/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92-%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/

Publish date：April 26th 2024, 5:58:16 pm

Update date：April 26th 2024, 6:59:37 pm

License：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

Next Post

KMP算法
Previous Post

操作系统结构及进程管理

CATALOG

一、0-1背包问题
二、完全背包问题