帮助小明制定健康食谱

Question

问题描述
小明同学想要控制自己的体重，为此他决定制定一个健康膳食计划，其目标是在保证身体必须的营养的前提下尽量少吃东西，由于每天能买到的食物种类众多，每种食物含有的营养物质又各不相同，所以他想要利用计算机帮助自己规划每日健康食谱，请你用所学《数据与算法》的知识帮助小明同学制定他的健康食谱。
输入格式
输入由三部分组成：
第1行前两个整数分别表示当日需要的营养物质种类数 N 和当日可以买到的食物种类数 M，其中 1<=N<=16，16种营养物质分别用编号0到15表示。
1<=M<=216=65536，后 M 个整数分别表示当日能买到的 M 种食物各自对应的营养物质种类的数量；
第2行为 N 个整数，表示当日需要的营养物质列表，按数字大小升序排列；
第3到M+2行为每种食物自己含有的营养物质列表，按数字大小升序排列，且食物自身的序号按行数从上到下依次编为0到M - 1号，需要注意，食物中可能含有当日不需要的营养物质，对于此类营养物质可以摄入也可以不摄入。
输出格式
输出为1行，为当日计划吃的食物，用空格分隔，且按数字大小升序排列，如果没有合适的食谱，则输出-1，题目数据保证如果有解，则解是唯一的。
输入样例
3 3 1 1 2
1 4 6
1
4
4 6
输出样例
0 2
提示

1. 采用动态规划方法求解，得到满足营养需求的最佳食物组合（即所需食物数量最小的组合）；
2. 可以使用unsigned short ntemp[16]记录当日需要的营养物质列表；
3.  可以考虑采用位运算提升程序效率，比如输入的营养序号为2和3，则将它们转化为二进制数0100和1000，可以使用unsigned short N 表示需要的营养物质列表的二进制数1100（对应的十进制数为12）；
4. DP更新策略：
       a. 对于每种营养需求状态 s，我们遍历从65535到1的整数 s，表示我们按照从高位到低位的顺序依次考虑每一种营养物质;
       b. 遍历所有的食物：对于每个食物，判断它是否包含当前状态 s 所需的营养物质。如果使用当前食物可以得到一个更优的解，更新该状态 s 下的相关数组。

Answer 1

引自强大而免费的微信小程序：皆我百晓生。

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

vector<int> bestPlan;
vector<int> nutrientNeeded;
vector<vector<int>> foods;

bool canSatisfy(int food, int nutrientNum) {
    for (int i = 0; i < nutrientNum; i++) {
        if (nutrientNeeded[i] > 0 && foods[food][i] > 0) {
            return false;
        }
    }
    return true;
}

void updateNeeded(int food, int nutrientNum, bool negative) {
    for (int i = 0; i < nutrientNum; i++) {
        if (negative) {
            nutrientNeeded[i] -= foods[food][i];
        } else {
            nutrientNeeded[i] += foods[food][i];
        }
    }
}

void solve(int nutrientNum, int foodNum) {
    vector<int> dp(1 << foodNum, -1);
    vector<int> prev(1 << foodNum, -1);

    int maxStatus = (1 << foodNum) - 1;

    dp[0] = 0;

    for (int status = 0; status <= maxStatus; status++) {
        for (int food = 0; food < foodNum; food++) {
            if ((status & (1 << food)) == 0) {
                int nextStatus = status | (1 << food);
                if (canSatisfy(food, nutrientNum) && dp[nextStatus] == -1) {
                    dp[nextStatus] = dp[status] + 1;
                    prev[nextStatus] = status;
                }
            }
        }
    }

    int foodStatus = maxStatus;
    while (foodStatus != 0) {
        int prevStatus = prev[foodStatus];
        for (int food = 0; food < foodNum; food++) {
            if ((prevStatus & (1 << food)) == 0 && (foodStatus & (1 << food)) != 0) {
                bestPlan.push_back(food);
            }
        }
        foodStatus = prevStatus;
    }

    sort(bestPlan.begin(), bestPlan.end());
}

int main() {
    int nutrientNum, foodNum;
    cin >> nutrientNum >> foodNum;
    foods.resize(foodNum);

    for (int i = 0; i < foodNum; i++) {
        foods[i].resize(nutrientNum);
        for (int j = 0; j < nutrientNum; j++) {
            cin >> foods[i][j];
        }
    }

    nutrientNeeded.resize(nutrientNum);
    for (int i = 0; i < nutrientNum; i++) {
        cin >> nutrientNeeded[i];
    }

    solve(nutrientNum, foodNum);

    for (int i = 0; i < bestPlan.size(); i++) {
        cout << bestPlan[i] << " ";
    }
    cout << endl;

    return 0;
}