算法设计与分析作业4

一、01背包问题

给定：

• 价值数组 v = {8, 10, 6, 3, 7, 2}
• 重量数组 w = {4, 6, 2, 2, 5, 1}
• 背包容量 c = 12

解决方案分析

1. 二维动态规划

定义 m[i,j]：从前 i 个物品中选择，总体积不超过 j 的最大价值。

• 如果 j < w[i-1]：m[i,j] = m[i-1,j]（不能选择第 i 个物品）
• 否则：m[i,j] = max(m[i-1,j], m[i-1,j-w[i-1]] + v[i-1])（选择或不选择第 i 个物品）

1.1 动态规划表 m[i,j] 的构建

i=0/j=0: m[i,j]=0

i\j	0	1	2	3	4	5	6	7	8	9	10	11	12
0	0	0	0	0	0	0	0	0	0	0	0	0	0

i=1 (物品1，重量=4，价值=8):

• w[0]=4, v[0]=8 → 如果 j >= 4，则 m[1,j] = max(m[0,j], m[0,j-4]+v[0])
• 因此，m[1,4→12] = 8

i\j	0	1	2	3	4	5	6	7	8	9	10	11	12
1	0	0	0	0	8	8	8	8	8	8	8	8	8

i=2 (物品2，重量=6，价值=10):

• w[1]=6, v[1]=10 → 如果 j >= 6，则 m[2,j] = max(m[1,j], m[1,j-6]+v[1])
• 如果 j < 6，则 m[2,j] = m[1,j]
• 因此，m[2,6] = max(m[1,6]=8, m[1,0]+10=10) → 10
• 类似地，m[2,7] = 10，一直到 m[2,12] = max(m[1,12]=8, m[1,6]+10=18) → 18
  | i\j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
  | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
  | 2 | 0 | 0 | 0 | 0 | 8 | 8 | 10 | 10 | 10 | 10 | 18 | 18 | 18 |
  i=3 (物品3，重量=2，价值=6):
• w[2]=2, v[2]=6 → 如果 j >= 2，则 m[3,j] = max(m[2,j], m[2,j-2]+v[2])
• 如果 j < 2，则 m[3,j] = m[2,j]
• 因此，m[3,2] = max(m[2,2]=0, m[2,0]+6=6) → 6
• m[3,4] = max(m[2,4]=8, m[2,2]+6=6) → 8
• m[3,6] = max(m[2,6]=10, m[2,4]+6=8+6=14) → 14
• m[3,8] = max(m[2,8]=10, m[2,6]+6=10+6=16) → 16
• m[3,10] = max(m[2,10]=18, m[2,8]+6=10+6=16) → 18
• m[3,12] = max(m[2,12]=18, m[2,10]+6=18+6=24) → 24

i\j	0	1	2	3	4	5	6	7	8	9	10	11	12
3	0	0	6	6	8	8	14	14	16	16	18	18	24

i=4 (物品4，重量=2，价值=3):

• j=4：max(8, m[3,2]+3) = max(8, 6+3) = 9
• j=6：max(14, m[3,4]+3) = max(14, 8+3) = 14
• j=8：max(16, m[3,6]+3) = max(16, 14+3) = 17
• j=10：max(18, m[3,8]+3) = max(18, 16+3) = 19
• j=12：max(24, m[3,10]+3) = max(24, 18+3) = 24

i\j	0	1	2	3	4	5	6	7	8	9	10	11	12
4	0	0	6	6	9	9	14	14	17	17	19	19	24

i=5 (物品5，重量=5，价值=7):

• j=11：max(19, m[4,6]+7) = max(19, 14+7) = 21
• j=12：max(24, m[4,7]+7) = max(24, 14+7) = 24

i\j	0	1	2	3	4	5	6	7	8	9	10	11	12
5	0	0	6	6	9	9	14	14	17	17	19	21	24

i=6 (物品6，重量=1，价值=2):

• j=1：max(0, m[5,0]+2) = max(0, 0+2) = 2
• j=3：max(6, m[5,2]+2) = max(6, 6+2) = 8
• j=4：max(9, m[5,3]+2) = max(9, 6+2) = 9
• j=5：max(9, m[5,4]+2) = max(9, 9+2) = 11
• j=7：max(14, m[5,6]+2) = max(14, 14+2) = 16
• j=9：max(17, m[5,8]+2) = max(17, 17+2) = 19
• j=12：max(24, m[5,11]+2) = max(24, 21+2) = 24

i\j	0	1	2	3	4	5	6	7	8	9	10	11	12
6	0	2	6	8	9	11	14	16	17	19	19	21	24

1.2 代码实现

#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int v[1001], w[1001], f[1001][1001];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i-1][j];
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i-1][j-v[i]] + w[i]);
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            cout << f[i][j] << "\t";
        }
        cout << endl;
    }
    cout << f[n][m] << endl;
    return 0;
}

1.3 回溯找出最优组合

• 从 i=6, j=12 开始回溯
• 比较 m[6,12] 和 m[5,12]，若相等则不选第6个物品
• 继续比较 m[5,12] 和 m[4,12]，若相等则不选第5个物品
• 比较 m[4,12] 和 m[3,12]，若相等则不选第4个物品
• 比较 m[3,12] 和 m[2,12]，若 m[3,12] > m[2,12] 则选第3个物品，剩余容量 12-2=10
• 比较 m[2,10] 和 m[1,10]，若 m[2,10] > m[1,10] 则选第2个物品，剩余容量 10-6=4
• 比较 m[1,4] 和 m[0,4]，若 m[1,4] > m[0,4] 则选第1个物品，剩余容量 4-4=0
  最终选择的物品是第1、2、3个，总重量 4+6+2=12，总价值 8+10+6=24。

2. 一维动态规划

2.1 为什么可以这样变形？

在二维动态规划中，m[i,j] 可以得到任意 i 和 j 的合法最优解，但当我们只需要最终状态 m[n,m] 时，可以使用一维空间来更新状态。

2.2 状态定义 f[j]

f[j]：前 n 个物品，背包容量为 j 时的最优解。

2.3 为什么一维情况下需要逆序枚举背包容量？

在二维情况下，m[i,j] 依赖于前一轮 i-1 的状态，且 m[i,j] 和 m[i-1,j] 是独立的。优化为一维后，如果按正序更新，可能会使用到已经更新过的状态 i 而不是 i-1 的状态。

2.4 代码实现

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N, V;
    cin >> N >> V;
    int v[1001], w[1001], state[1001] = {0};
    for (int i = 1; i <= N; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= v[i]; j--) {
            state[j] = max(state[j], state[j - v[i]] + w[i]);
        }
    }
    cout << state[V] << endl;
    return 0;
}

---

状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] 。

二、流水调度算法

Given:

$$n=7\\(a_0,a_1,a_2,a_3,a_4,a_5,a_6) = (5,3,6,4,8,9,6)\\(b_0\ ,b_1,b_2,b_3,\ b_4,b_5,\ b_6) = (2,4,7,2,9,7,3)$$

约翰逊算法步骤

划分集合：

集合A:

$$a_i ≤ b_i:作业1（3≤4）、作业2（6≤7）、作业4（8≤9）$$

集合B

$$a_i > b_i：作业0（5>2）、作业3（4>2）、作业5（9>7）、作业6（6>3）$$

排序规则：

集合A按升序排列：作业1 → 作业2 → 作业4

集合B按降序排列：作业5→ 作业6→ 作业3→ 作业0

合并顺序：

最终作业顺序：[1, 2, 4, 5, 6, 3, 0]

调度甘特图

4-2.png

最短用时 43