P1164. 模板题_小A点菜

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 523 阅读时长 ≈ 2 分钟

考点

  • 01背包

题解

见思路

思路

二维数组实现

经典的01背包问题，每种元素只有一个，且只有选或不选两种状态；题目要求多少种选法能刚好花光m元

可以设dp[i][j]为前i个元素花了j元，显然有动态转移方程如下： \[ \underset{\text{前}i-1\text{个元素花}j\text{元}}{\underbrace{dp\left[ i-1 \right] \left[ j \right] }}+\underset{\text{选第}i\text{个元素，前}i-1\text{个元素应花}j-\cos t\left[ i \right] \text{元}}{\underbrace{dp\left[ i-1 \right] \left[ j-\cos t\left[ i \right] \right] }}\rightarrow dp\left[ i \right] \left[ j \right] \] 我们最终要计算的就是dp[n][m]，即前n个元素花了m元的情况

本题的临界值应该在j == 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
#include <bits/stdc++.h>

using namespace std;

int dp[101][10050], cost[101];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> cost[i];
    for (int i = 0; i <= n; ++i)
        dp[i][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            dp[i][j] += dp[i - 1][j];
            if (j >= cost[i])
                dp[i][j] += dp[i - 1][j - cost[i]];
        }
    }
    cout << dp[n][m];
    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
#include <bits/stdc++.h>

using namespace std;

int dp[10050], cost[101];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> cost[i];
    dp[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = m; j >= cost[i]; --j)
        {
            dp[j] += dp[j - cost[i]];
        }
    }
    cout << dp[m];
    return 0;
}