帮帮我，感激不尽。赏关注
有 n 个人在排队取餐。每个人都有自己的口味偏好，他们会在手机上自助选择好自己想要的餐品。不同的餐品需要不同的制作时间。
你是这家餐厅的老板，作为生意火爆的网红打卡点，你的餐厅营业时间一天只有m分钟。如果某个顾客能够吃到他点的餐品，他会就给餐厅打分。第i个人如果吃到了餐品，他就会给餐厅打x[i]分。但是由于不能马上吃到餐品，顾客就会产生不满。如果第i个人吃到餐品等待了q分钟，他就会减少打分，分数就会减少q∗y[i]，这里y[i]表示顾客每分钟产生的不满度。并且每个顾客有一个等待爆发周期z[i]，即每隔z[i]分钟会直接降低打分30分。当然，只要顾客吃到了餐品，他至少会给餐厅打原本分数的一半。
作为老板，你当然是可以看到所有顾客的要求的。为了让你的餐厅的总分尽量高，你决定调整出餐的顺序。请你根据给出的顾客要求，来安排出餐顺序获得最高的总分。当然不一定每位顾客都能在营业时间内获得餐品。
【输入格式】
第一行输入两个数n,m，表示共有n个人，营业时间为m分钟
接下来输入n行，每行输入四个数x[i],y[i],z[i]，t[i]。x[i]表示第i个顾客如果吃到餐品会打的最高分数，y[i]表示每分钟产生的不满度，z[i]表示等待爆发周期，每个周期减少30分。t[i]表示制作该餐品所需要花费的时间。
【输出格式】
输出一行一个数，表示获得的最高总分。
【输入样例】
2 100
1000 4 30 50
500 2 50 50
【输出样例】
1020
【数据范围】
对于70%的数据，保证n≤10
对于100%的数据，保证n≤20,m≤1000,1≤x[i]≤10000,0≤y[i]≤100,1≤z[i]≤100,1≤t[i]≤100
每个顾客初始的最高分数保证是10的倍数。
这道题目可以使用状态压缩动态规划来解决。我们可以定义状态f[j]表示状态为j时的最大总分。其中j是一个二进制数，第k位为1表示第k个顾客已经吃到了餐品。
然后我们可以枚举下一个出餐的顾客是谁，然后更新状态。具体地，我们可以枚举所有未吃到餐品的顾客k，然后计算出他吃到餐品时的打分，然后更新状态f[j | (1 << k)]。
最后答案就是所有状态中的最大值。
这种方法的时间复杂度为O(m * 2^n * n)，其中n为顾客数量，m为营业时间。
已收到消息. 这道题目可以使用状态压缩动态规划来解决。我们可以定义状态f[j]表示状态为j时的最大总分。其中j是一个二进制数，第k位为1表示第k个顾客已经吃到了餐品。 然后我们可以枚举下一个出餐的顾客是谁，然后更新状态。具体地，我们可以枚举所有未吃到餐品的顾客k，然后计算出他吃到餐品时的打分，然后更新状态f[j | (1 << k)]。 最后答案就是所有状态中的最大值。 这种方法的时间复杂度为O(m * 2^n * n)，其中n为顾客数量，m为营业时间。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20, M = 1 << N;
int n, m;
int x[N], y[N], z[N], t[N];
int f[M];
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ ) cin >> x[i] >> y[i] >> z[i] >> t[i];
memset(f, -0x3f, sizeof f);
f[0] = 0;
for (int i = 0; i < m; i ++ )
for (int j = 0; j + 1 < 1 << n; j ++ )
{
if (f[j] == -0x3f3f3f3f) continue;
f[j] = max(f[j], f[j]);
for (int k = 0; k < n; k ++ )
if (!(j >> k & 1))
{
int score = x[k] - y[k] * (i + t[k]) - (i + t[k]) / z[k] * 30;
score = max(score, x[k] / 2);
f[j | 1 << k] = max(f[j | 1 << k], f[j] + score);
}
}
int res = 0;
for (int i = 0; i < 1 << n; i ++ ) res = max(res, f[i]);
cout << res << endl;
return 0;
}
- 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/722479
- 除此之外, 这篇博客: C语言简单的单步调试中的 4.这里先介绍一下这几个常用的功能键：①是用于开始调试；②是用于逐行执行，也就是黄色的小标识会跑到下一行；③是用于进入函数体，如果直接逐行执行则不会进入到其他函数中；④和③相反，从函数体中退出来，回到main函数继续执行。其他按键自己有兴趣可以去查查资料，这里就不讲了，①旁边的那个在多行调试中会用到。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^