[Algorithm][动态规划][完全背包问题]详细讲解_完全背包问题 动态规划

1.题目链接

• [模板]完全背包

2.算法原理详解

• 思路：

  • 确定状态表示 -> dp[i][j]的含义

    • 不要求恰好装满
      • dp[i][j]：从前i个物品中挑选，总体积不超过j，所有选法中，能挑选出来的最大价值
    • 要求恰好装满
      • dp[i][j]：从前i个物品中挑选，总体积恰好等于j，所有选法中，能挑选出来的最大价值

  • 推导状态转移方程：根据最后一个位置的情况，分情况讨论

    • 不要求恰好装满：j - v[i] >= 0是为了确保背包此时容量足够塞下当前物品
      

    • 要求恰好装满：dp[i][j] == -1表示没有这种情况，即此时总体积凑不到j
      

  • 初始化：

    • 不要求恰好装满：vector<vector<int>> dp(n + 1, vector<int>(V + 1))
    • 要求恰好装满：第一行除第一个位置，其余都为-1

  • 确定填表顺序：从上往下，从左往右

  • 确定返回值：

    • 不要求恰好装满：dp[n][V]
    • 要求恰好装满：dp[n][V] == -1 ? 0 : dp[n][V]
• 滚动数组优化空间

  • 每次填值，只依赖上一行及左边列的值

    • 所以，理论上只需要两行一维数组，就可以解决问题

  • 可以一个一维数组就优化掉此问题

    • 从左往右遍历该数组，就不会影响动态规划的规程
      

  • 操作

    • 删除所有的横坐标
    • 修改一下j的遍历顺序

  • 注意：不要去强行解释优化后的妆台表示以及状态转移方程，费时费力还没啥意义

3.代码实现

// v1.0
int main()
{
    int n = 0, V = 0;
    cin >> n >> V;

    vector<int> v(n + 1), w(n + 1);
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(V + 1));
    
    // Q1
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= V; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i])
            {
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
            }
        }
    }
    cout << dp[n][V] << endl;

    // Q2
    dp.resize(n +1, vector<int>(V + 1));
    for(int i = 1; i <= V; i++)
    {
        dp[0][i] = -1;
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= V; j++) // 下标从0开始
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= v[i] && dp[i][j - v[i]] != -1)
            {
                dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]);
            }
        }
    }
    cout << (dp[n][V] == -1 ? 0 : dp[n][V]) << endl;

    return 0;
}
--------------------------------------------------------------------------
// v2.0 滚动数组优化
int main()
{
    int n = 0, V = 0;
    cin >> n >> V;

    vector<int> v(n + 1), w(n + 1);
    for(int i = 1; i <= n; i++)
    {
        cin >> v[i] >> w[i];
    }

    vector<int> dp(V + 1);
    
    // Q1
    for(int i = 1; i <= n; i++)
    {
        for(int j = v[i]; j <= V; j++)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout << dp[V] << endl;

    // Q2
    dp.resize(V + 1);
    for(int i = 1; i <= V; i++)
    {
        dp[i] = -1;
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = v[i]; j <= V; j++)
        {
            if(dp[j - v[i]] != -1)
            {
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
            }
        }
    }
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96