小A点菜

题目背景

uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。

uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过 uim 由于买了一些书，口袋里只剩 $M$ 元 $(M \le 10000)$。

餐馆虽低端，但是菜品种类不少，有 $N$ 种 $(N \le 100)$，第 $i$ 种卖 $a_i$ 元 $(a_i \le 1000)$。由于是很低端的餐馆，所以每种菜只有一份。

小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。

由于小 A 肚子太饿，所以最多只能等待 $1$ 秒。

输入格式

第一行是两个数字，表示 $N$ 和 $M$。

第二行起 $N$ 个正数 $ai$ (可以有相同的数字，每个数字均在 $1000$ 以内)。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

样例 #1

样例输入 #1

4 4
1 1 2 2

样例输出 #1

3

样例 #2

注: 本样例原题无, 是我额外添加的

样例输入 #2

10 9
1 2 3 4 5 6 7 8 9 10

样例输出 #2

8

提示

2020.8.29，增添一组 hack 数据 by @yummy

作答:

错误作答:

核心思想是, 像 01背包一样dp, 状态也是, 只不过额外加一个变量在 if (dp[i] == okane) 时, 进行自增.

实际上这样是不对的, 因为在01背包dp过程中会 dp[i] 的值 一直是最优的, 所以可能会丢失某些情况, 光靠 额外变量自增进行记录 是远远不够的!

#include <stdio.h>

void do_11(void)
{
    int n, m;
    scanf("%d %d", &n, &m);
    int* arr = new int[n];
    int* DP = new int[m + 1];
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &arr[i]);
    }

    // init 初始状态
    DP[0] = 0;
    for (int j = 1; j <= m; ++j)
    {
        DP[j] = arr[0];
    }

    // 完全不对 零昏
    // 同01背包, 只是为0的时候需要进行一次 zero_cont++
    int zeor_cont = 0; // 计数君

    if (arr[0] == m)
        ++zeor_cont;

    for (int i = 1; i < n; ++i)
    {
        for (int j = m; j > 0; --j)
        {
            if (j - arr[i] >= 0)
            {
                // 如果提前达到了, 那么就会重复加, 而后面的也没有计算!
                // 不是这样滴艹, 即使修改了也不对

                if (DP[j] == m)
                    ++zeor_cont;

                DP[j] = getMax(DP[j], DP[j - arr[i]] + arr[i]);

                if (DP[j] == m)
                    ++zeor_cont;
            }
        }
    }

    printf("%d", zeor_cont);
}

C++

正解:

分析: 「状态 の 含义」

首先, 是 "正好把钱花光", "方法数" 这些关键限定.

然后, 参考 01背包, 因为本题也是 "每道菜只能点一次", 所以 对于每一个状态 我们可以想到这也是一个 点 与 不点 的关系.

或许你又疑问了: 为什么可以用动态规划?!

动态规划实际上就是为了解决 "重叠子问题", 来降低时间复杂度的.

那么 第 $i$ 道菜, 正好花完钱的方法数, 是否与 第 $i - 1$ 道有关?

分析见下:

有疑问就是你造化不够

我们可以参照 01背包 (tmd 我也说不清楚了)

// 状态含义
/**
 * 只有两种选择: 点 与 不点
 * 则 DP[i][j] 含义 就是 点 或 不点 第 i 道菜, 剩余 金钱在j的处的方法数
 * 如果 j - okane[i] > 0, 则 DP[i][j] = DP[i - 1][j] + DP[i - 1][j - okane[i]]
 * 如果 j - okane[i] == 0, 则 DP[i][j] == DP[i - 1][j] + 1
 * 如果 j - okane[i] < 0, 沿用之前的方法 DP[i][j] = DP[i - 1][j]
 */

// 状态压缩
/**
 * 如果从后面算起, 那么就没有问题 {[i]域}
 */

开个玩笑，这是一道简单的动规题，定义f[i][j]为用前i道菜用光j元钱的办法总数，其状态转移方程如下：

（1）if(j==第i道菜的价格)f[i][j]=f[i-1][j]+1;

（2）if(j>第i道菜的价格) f[i][j]=f[i-1][j]+f[i-1][j-第i道菜的价格];

（3）if(j<第i道菜的价格) f[i][j]=f[i-1][j];

说的简单一些，这三个方程，每一个都是在吃与不吃之间抉择。
若钱充足，办法总数就等于吃这道菜的办法数与不吃这道菜的办法数之和；
若不充足，办法总数就只能承袭吃前i-1道菜的办法总数。
依次递推，在最后，我们只要输出f[n][m]的值即可。

偷来的题解

方法数 动态规划解释

#include <stdio.h>

int main(void)
{
    int n, m;
    scanf("%d %d", &n, &m);
    int* arr = new int[n];
    int* DP = new int[m + 1];
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &arr[i]);
    }

    // init 初始状态
    for (int j = 0; j <= m; ++j)
    {
        DP[j] = 0;
    }
    // 状态含义
    /**
     * 只有两种选择: 点 与 不点
     * 则 DP[i][j] 含义 就是 点 或 不点 第 i 道菜, 剩余 金钱在j的处的方法数
     * 如果 j - okane[i] > 0, 则 DP[i][j] = DP[i - 1][j] + DP[i - 1][j - okane[i]]
     * 如果 j - okane[i] == 0, 则 DP[i][j] == DP[i - 1][j] + 1
     * 如果 j - okane[i] < 0, 沿用之前的方法 DP[i][j] = DP[i - 1][j]
     */

    // 状态压缩
    /**
     * 如果从后面算起, 那么就没有问题 {[i]域}
     */


    // 状态转移方程
    // DP[i][j] = 

    for (int i = 0; i < n; ++i)
    {
        for (int j = m; j > 0; --j)
        {
            if (j - arr[i] == 0)
                DP[j] += 1;
            else if (j - arr[i] > 0)
                DP[j] = DP[j] + DP[j - arr[i]];
        }
    }

    printf("%d", DP[m]);
    return 0;
}

C++