P1164 小A点菜（洛谷训练场）题解

水深无声 2022-12-28 07:26 131阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入格式
     *  输出格式
     *  输入
     *  输出
 *  算法分析
 *  解题标程（二维dp）
 *  算法优化
 *   *  优化代码（一维dp）

--------------------

# 题目描述 #

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

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

不过`uim`由于买了一些`辅（e）辅（ro）书`，口袋里只剩 M 元 ( M ≤ 10000 )。

餐馆虽低端，但是菜品种类不少，有 N 种 ( N ≤ 100 )，第 i 种卖 ai 元 ( a\_i ≤ 1000 )。

由于是很低端的餐馆，所以每种菜只有一份。

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

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

## 输入格式 ##

> 第一行是两个数字，表示 N 和 M。  
> 第二行起 N 个正数 ai（可以有相同的数字，每个数字均在1000以内）。

## 输出格式 ##

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

## 输入 ##

4 4
    1 1 2 2

## 输出 ##

# 算法分析 #

注意这道题**与01背包的区别在于这道题需要求出刚好花完 M 元的点菜方案**  
解题算法有两种（重点讲dp）:

*  1、用dfs深搜去解决这个问题，遍历所有的菜品，将最后菜品总价等于 M 的所有方案统计起来，但是这个算法会存在超时风险。*（由于`小A`肚子太饿，所以最多只能等待1秒。）*
 *  2、用dp动态规划解决，状态为前 i 种菜品中选择不大于价格 j 元的点菜方案数。
 *  这道题dp有三个情况需要去考虑
 *  (1) 当第 i 个菜的价格刚好等于价格 j 时：  
    `if(v[i]==j) dp[i][j]=dp[i-1][j]+1`
 *  (2) 当第 i 个菜的价格大于价格 j 时：  
    `if(v[i]>j) dp[i][j]=dp[i-1][j]`
 *  (3) 当第 i 个菜的价格小于价格 j 时：  
    `if(v[i]<j) dp[i][j]=dp[i-1][j]+dp[i-1][j-v[i]];`

# 解题标程（二维dp） #

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    int n,m;
    int v[105];
    int dp[105][10005];
    
    int main()
    {
        
        cin >> n >> m;
        
        for(int i=1;i<=n;i++)
            cin >> v[i];
        
        for(int i=1;i<=n;i++){
        
            for(int j=0;j<=m;j++){
        
                if(v[i]==j)
                    dp[i][j]=dp[i-1][j]+1;
                else if(v[i]>j)
                    dp[i][j]=dp[i-1][j];
                else
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-v[i]];
            }
        }
        
        cout << dp[n][m] << endl;
        
        return 0;
    }

# 算法优化 #

上述算法是用二维dp数组去进行dp表的计算，这里**可以将二维dp表转化为一维dp表**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

*  图片来源：（侵权联系删除）  
    ![在这里插入图片描述][20201215143730910.png]

## 优化代码（一维dp） ##

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    int n,m;
    int v[105];
    int dp[10005];
    
    int main()
    {
        
        cin >> n >> m;
        
        for(int i=1;i<=n;i++)
            cin >> v[i];
        
        dp[0]=1;
        for(int i=1;i<=n;i++){
        
            for(int j=m;j>=v[i];j--){
        
                dp[j]=dp[j]+dp[j-v[i]];
            }
        }
        
        cout << dp[m] << endl;
        
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/bade41c1ecc5490e8308368f60a1ee52.png
[20201215143730910.png]: https://img-blog.csdnimg.cn/20201215143730910.png