OrderFood 点菜

Lily 点菜问题 背包问题

题目:

Lily非常喜欢旅游，经常和他老婆自驾出游。但是Lily是一个非常讲求性价比的程序员，所以每次在外面吃饭的时候都要控制价格。今年国庆Lily和他老婆出游，Lily规定每顿饭的价格上限为n，他老婆想点k个菜，餐厅提供m个菜。
请问，在不超过Lily价格上限的情况下，点k个菜有多少种点法（同一种菜只能点一份）。  

 输入：
 1、第一行为价格上限n，想点菜的个数k，以及菜品个数m 
 2、接下来m行，每行一个菜品价格 
 3、以上输入均为正整数  
 输出：
 1、输出为一行，代表点菜的方案数  
 Sample Input:
 10 2 4 
 10 
 3 
 5 
12   
Sample Output:
 1   

（Sample说明：因为需要点两个菜，且总价不超过10，所以只能有第二和第三个菜的组合方案。其他方案加起来都会超过10）

见到的动态规划一般是一维dp[i]和二维的dp[i][j]。没见过三维的，就搞不出来。经过ACM同学的指点，再加一维，就解决了。

为什么再加一维呢，因为这里有k个菜的约束。不像一般的求最大重量那样的问题。

转移方程如下:

// dp[i][j][k] 代表前i个菜，预算刚好为j，选取k个菜的方案总数
// dp[i][j][k] = dp[i-1][j-food[i]][k-1] (food[i]加进去) + dp[i-1][j][k](food[i]不加进去)
// 时间复杂度和空间复杂度都为: O(mnk), m、n、k分别是题目中的数据，分别代表预算，选择个数，菜品总数

具体代码如下:

#ifndef AGORITHM_ORDERFOOD_H
#define AGORITHM_ORDERFOOD_H

#include <vector>
#include <iostream>

using namespace std;

class OrderFood {
public:
    // dp[i][j][k] 代表前i个菜，预算刚好为j，选取k个菜的方案总数
    // dp[i][j][k] = dp[i-1][j-food[i]][k-1] (food[i]加进去) + dp[i-1][j][k](food[i]不加进去)
    // 时间复杂度和空间复杂度都为: O(mnk), m、n、k分别是题目中的数据，分别代表预算，选择个数，菜品总数
    static int answer1(int budget, int tot, std::vector<int> &foods) {
        const int N = foods.size();

        vector<vector<vector<int>>> dp(N, vector<vector<int>>(budget + 1, vector<int>(tot + 1, 0)));

        dp[0][foods[0]][1] = 1;

        for (int i = 1; i < N; i++) {
            for (int j = 1; j <= budget; j++) {
                int prevBudget = j - foods[i];
                for (int k = 1; k <= tot; k++) {
                    if (prevBudget >= 0) {
                        if (prevBudget == 0 && k == 1) {    // new entry
                            dp[i][j][k] += 1;
                        } else {
                            dp[i][j][k] += dp[i - 1][j - foods[i]][k - 1];  // plus previous one
                        }
                    }
                    dp[i][j][k] += dp[i - 1][j][k];
                }
            }
        }


        int count = 0;
        for (int j = 1; j <= budget; j++) {
            count += dp[N - 1][j][tot];
        }

        return count;
    }


    static void test() {
//        int n = 10, k = 2, m = 4;
//        std::vector<int> foods = {10, 3, 5, 12};
        int n, k, m;
        cin >> n >> k >> m;
        std::vector<int> foods(m, 0);
        for (int i = 0; i < m; i++) {
            cin >> foods[i];
        }
        std::cout << "answer: " << answer1(n, k, foods) << endl;
    }
};


#endif //AGORITHM_ORDERFOOD_H