原题大意

有r种菜谱，有p种原料，每种原料都有相应的价格，已经有了m种原料，需要你做出n道菜，问最少需要花多少钱，注意：只要买了一种原料，下面如果还用到无需再买。输入的菜谱中，1表示需要这种原料，0表示不需要。

算法分析

刚开始，我想通过暴力+回溯，可是p的最大值可以取到13，结果，就超时了。后来看了网上的题解，算法应该这样设计：1.将菜谱当成2进制，然后用数组保存，因为最多有2^13种可能，数组开到9000就够了。2.用动态规划，每种菜谱要么选，要么不选，选了之后会对下面的选择造成影响，可以用记忆化搜索完成。

程序代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;


const int INFI = (1 << 20) - 1;
int r;// 菜谱数
int p;// 配料数
int m;//已有的配料数;
int n;//需要做出来的菜的数量
int cost[15];//每种原料的价格
vector<int> ing_have;//已经有的原料序号
int dp[35][1 << 13][35];//dp[i][j][k]，i表示第n道菜，j表示第n道菜的菜谱十进制表示，k表示已经选了k道菜时的最优解

int ing[35];//保存二进制菜谱的十进制数值

int Bin_to_Dec(int *into_int){//二进制转化为十进制
    int i, j;
    int ans = 0;
    for(i = 0, j = p - 1; j >= 0; j--,i++)
    {
        ans += into_int[j] *pow(2,i);
    }
    return ans;
}

int calculate_cost(int cur, int num){//cur表示已经买过的原料，num表示该菜谱所需的原料
    int Cost = 0;
    for(int i = 0; i < p; i++)
    {
        int x,y;
        x = cur % 2;
        y = num % 2;
        if(y == 1 && x == 0) //将cur，num再转化为二进制，判断哪些需要买，哪些已经买过 
          Cost += cost[p - i - 1];
        cur /= 2;
        num /= 2;
    }
    return Cost;
}

int solve(int idx, int cur, int cnt){
   if(cnt == n ) return 0;
   if(idx >= r) return INFI;

   int &ans = dp[idx][cur][cnt];
   if(ans != -1) return ans;
   int res = INFI;

   //做这道菜
   int incl = calculate_cost(cur, ing[idx]) + solve(idx + 1, (cur|ing[idx]),cnt+1);
   //按位或的运用

   res = min(incl, res);

   //不做这道菜
   int excl = solve(idx+1, cur, cnt);
   res = min(res, excl);
   ans = res;
   return ans;
}


int main(){
//freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d%d",&r, &p, &n, &m);
        ing_have.clear();
        int temp;
        for(int i = 0; i < m; i++)
            { scanf("%d", &temp);ing_have.push_back(temp);}
        for(int i = 0; i < p; i++)
            scanf("%d", &cost[i]);
        for(int i = 0; i < 35; i++)
            for(int j = 0; j < (1 << 13); j++)
                for(int k = 0; k < 35; k++)
                    dp[i][j][k] = -1;

        int into_int[15];//模拟一道菜的菜谱
        for(int i = 0; i < r; i++)
            {
                for(int j = 0; j < p; j++)
                    scanf("%d", &into_int[j]);
                ing[i] = Bin_to_Dec(into_int);
            }
            for(int i = 0; i < 15; i++)
                into_int[i] = 0;
            for(int i = 0; i < ing_have.size(); i++)
                into_int[ing_have[i]] = 1;

            printf("%d\n", solve(0, Bin_to_Dec(into_int), 0)); 
    }
    return 0;
}