倒水 问题描述 小秋家里来了n位客人，编号为1,2,3,...,n。现在小秋要给每一位客人倒水。 每个客人都有一个满意度，对于第i个客人，满意度是这样定义的： ·如果小秋给第i位客人倒了ai毫升水，客人的满意度为bi; ·如果小秋给第i位客人倒了ci(ci>ai)毫升水，客人的满意度为di; ·如果小秋给第i位客人倒的水不足ai毫升(可以为0),客人的满意度为ei; ·如果客人满意度已经是d;,继续给该客人倒水不会改变客人的满意度。 现在小秋有m毫升水，请问他要怎么样给客人倒水，才能让所有客人的满意度之和最大呢?你只需要求出所有客人满意度之和的最大值。 输入格式 第1行输入两个正整数n和m,表示客人的数量和小秋拥有水的体积。 接下来n行，每行五个整数ai,bi,ci,di,ei,第i行表示给第i位客人倒了ai毫升水满意度为b;,倒了ci毫升水满意度为d;,倒水不足ai毫升满意度为ei 输出格式 输出仅一行，包含一个整数，表示所有客人满意度之和的最大值。 样例输入 310 119100 -946540 -20210540 -30 说明/提示 对于20%的评测数据，1≤n≤20,1≤m≤100。 对于所有的评测数据，1≤n,m≤1000,1≤ai 我的答案：错的 一、信息 客人数量：n位客人，每位客人有特定的满意度条件。水的体积：小秋有m毫升水可分配。满意度条件：每位客人根据倒的水量有不同的满意度(bi, di, ei)，分别对应给定水量(ai)，超过给定水量(ci)，不足给定水量。 二、分析 题目的有用信息解析： n和m的范围：客人数量和水的体积限制了可能的分配方案。每位客人的满意度条件：这些条件决定了如何最优化分配水量以最大化总满意度。 思考过程和分析过程： 问题转化：这个问题可以被看作是一种特殊的背包问题，其中我们尝试在有限资源(水)的条件下最大化价值(满意度)。动态规划：考虑到每增加一个客人或者水量，我们可以基于之前的选择来更新最大满意度，这提示我们使用动态规划。 三、算法设计 状态定义：dp[i][j]代表考虑前i位客人，使用了j毫升水时，能够达到的最大满意度总和。转移方程： 对于每位客人，我们考虑三种情况：不足ai毫升，恰好ai毫升，超过ai但不超过ci毫升水，更新状态为这三种情况的最大值。dp[i][j] = max(dp[i-1][j], dp[i-1][j-ai] + bi, dp[i-1][j-ci] + di)，同时保证j-ai和j-ci不小于0，对于不足ai毫升，直接加上ei。初始化：dp[0][0] = 0，表示没有客人和水时的满意度为0。结果：遍历dp[n][0...m]，找出最大满意度总和。 四、代码实现 #include #include #include using namespace std; int main() { int n, m; cin >> n >> m; vector dp[0] = 0; // 初始化 for (int i = 0; i < n; ++i) { int a, b, c, d, e; cin >> a >> b >> c >> d >> e; vector for (int j = 0; j <= m; ++j) { if (j >= a) new_dp[j] = max(new_dp[j], dp[j-a] + b); if (j >= c) new_dp[j] = max(new_dp[j], dp[j-c] + d); new_dp[j] = max(new_dp[j], dp[j] + e); } dp = move(new_dp); } cout << *max_element(dp.begin(), dp.end()) << endl; return 0; } 五、实现代码过程中可能遇到的问题 初始化满意度：确保所有的满意度在没有水分配时被设置为最低可能值，除了dp[0]。内存限制：对于每位客人更新dp数组时，需要使用一个新的数组来避免在迭代过程中覆盖数据。最大满意度的计算：在动态规划的最后，需要找到在所有可能的水量分配下的最大满意度，这可能需要遍历整个dp数组。性能优化：对于大量的客人和水量，算法的时间复杂度和空间复杂度可能成为问题。在实际实现中，可能需要考虑进一步的优化方法，比如空间优化动态规划。 正确答案： 一、信息 客人数量和水的体积：n和m分别表示客人的数量和小秋拥有的水体积。满意度条件：每位客人有三种满意度状态，分别对应不同的水量。 二、分析 题目转化：将原问题转化为一个分组背包问题，每组包含三个物品，分别对应给客人倒0毫升水、ai毫升水、ci毫升水的情况。贪心分析：基于贪心策略，给客人倒水的量一定是0, ai, ci其中之一，以避免浪费水资源同时最大化满意度。状态定义：定义动态规划数组f[i][j]为考虑前i组物品，当前使用体积不超过j时的最大满意度。 三、算法设计 状态转移： 初始化：每轮开始时，f[i][j] = f[i-1][j] + e[i]，处理每组必选一个物品的情况。转移：分别处理选取0毫升水、ai毫升水、ci毫升水的情况，并更新最大满意度。空间优化：采用一维数组进行空间优化，逆序遍历背包容量，以避免更新冲突。 四、代码实现 #include using namespace std; typedef long long LL; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector for(int i = 1; i <= n; i++) { int a, b, c, d, e; cin >> a >> b >> c >> d >> e; for(int j = m; j >= 0; j--) { LL val = j >= 0 ? f[j] + e : LLONG_MIN; // 不给客人倒水的情况 if(j >= a) val = max(val, f[j - a] + b); // 倒ai毫升水 if(j >= c) val = max(val, f[j - c] + d); // 倒ci毫升水 f[j] = val; } } cout << *max_element(f.begin(), f.end()) << endl; // 输出最大满意度 return 0; } 五、实现代码过程中可能遇到的问题 枚举顺序：在进行动态规划状态转移时，需要从大到小枚举背包容量，以保证转移来自上一层的状态，避免当前层的更新影响后续的状态转移。初始化：确保动态规划数组正确初始化，考虑到每位客人至少会获得不倒水的满意度。数据范围和类型：考虑到满意度可能的值范围，使用long long类型以避免整数溢出。 六、复盘 错误原因： 问题转化：我没有从贪心算法的角度分析问题，即考虑到对于每个客人，我们只需要考虑三种情况（不倒水、倒ai毫升水、倒ci毫升水），而实际上这个洞察是将问题转化为分组背包问题的关键。每个客人相当于一个“组”，每组有三个选择，这正是分组背包问题的特征。 分组背包的理解：在分组背包问题中，每组内的物品（本题中的每位客人的三种倒水方案）之间是互斥的，即每组只能选取一项来加入背包（即为每位客人选择一种倒水方案）。我的解答中没有清楚地表达出这种每组必选一项的策略，也没有利用这一点来设计状态转移方程。 动态规划状态转移方程错误：我提供的状态转移方程没有正确处理每位客人三种倒水方案之间的关系，即没有为每种情况设计专门的状态转移逻辑。正确的做法应该是对每位客人分别处理不倒水、倒ai毫升水、倒ci毫升水的情况，并且更新满意度总和的最大值。 空间优化方法的错误理解：我没有提到如何正确进行空间优化。正确的方法是使用一维动态规划数组，并在更新时从后向前遍历，以避免在更新当前状态时覆盖还未使用的上一层状态，这一点在我的解答中被忽略了。 参考链接
您阅读本篇文章共花了：
发表评论