一、问题描述

二、问题分析

• 题目要求：
  • 有 $n$ 个苹果和 $1$ 个机器人，机器人一天最多吃 $m$ 个苹果。饲养员需要将 $n$ 个苹果分若干天喂给机器人，当投喂机器人 $i$ 个苹果时，可以获得 $A[i]$的快乐值。问如何分配苹果使得总快乐值最大？
• 问题本质 – 资源分配优化
  • 有 $n$ 个单位资源（苹果）
  • 有 $m$ 种投资方式（投喂不同数量的苹果）
  • 每种投资方式：消耗 $i$ 个单位资源，获得 $A[i]$的收益
  • 目标：在资源总量限制下最大化总收益
• 约束条件
  • 可重复选择：同一种投喂方式可以多天重复使用
  • 整数约束：苹果个数必须是整数
  • 投喂顺序不影响总快乐值

三、算法设计

• 首先很容易想到贪心策略

  • 优先选择快乐值最高的投喂方式，尽可能多地使用该方式，然后处理剩余苹果。

  • int main() {
        int n, m;
        cin >> n >> m;
    
        vector<pair<int, int>> A;
        for (int i = 1; i <= m; i++) {
            int happiness;
            cin >> happiness;
            A.push_back({i, happiness});
        }
    
        sort(A.begin(), A.end(), [](auto a, auto b) {
            if (a.second != b.second) return a.second > b.second; // 按照快乐值降序排序
            return a.first < b.first;  // 按照提供苹果个数升序排序
        });
    
        int ans = 0;
        for (auto a : A) {
            ans += a.second * (n / a.first);
            n %= a.first;  // 剩余的苹果数目
            if (n <= 0) break;
        }
        cout << ans << endl;
    
        return 0;
    }
    

  • 这种方法不能保证全局最优。 样例 $2$ 失败示例：

    • 输入 $n=4,m=3,A=[1,60,100]$。
    • 先排序：按快乐值降序，得到 $(3,100),(2,60),(1,1)$。
    • 贪心：先投喂 $3$ 个苹果（快乐值 $100$ ），剩余 $1$ 个苹果投喂 $1$ 个（快乐值 $1$ ），总快乐值 $101$。
    • 但正确答案是 $120$（投喂两天 $2$ 个苹果：$60+60=120$）。贪心策略错过了更优组合。

• 重新审视题目：

  • 根据先前的问题分析，会发现本题类似于无限背包问题，因为每天投喂可以视为一种物品（苹果数为重量，快乐值为价值），每种物品可无限使用，总苹果数需恰好为n：
    • 背包容量： $n$ 个苹果
    • 物品：投喂 $i$ 个苹果（重量 $=i$，价值$=A[i]$）
  • 动态规划解法

    • 状态定义
      $dp[i]$ 为已经喂养 $i$ 个苹果时能够获得的最大快乐值

    • 状态转移方程
      对于 $i$ 个苹果，考虑最后一天投喂（投喂后苹果数量为 $i$）的苹果数量 $j$ （$1\le j\le min(i,m)$）

      dp[i] = max(dp[i], dp[i - j] + A[j])
      

      • $dp[i]$：投喂 $i$ 个苹果能获得的最大快乐值
      • $dp[i-j]$：投喂 $(i-j)$ 个苹果能获得的最大快乐值
      • $A[j]$：某一天投喂 $j$ 个苹果获得的快乐值

    • 算法步骤

      • 初始化：
        $dp$ 数组大小为 $n+1$ ,初始值为 $0$
      • 对于 $i$ 从 $1$ 到 $n$：
        • 对于 $j$ 从 $1$ 到 $min(i,m)$：
        • dp[i] = max(dp[i], dp[i-j] + A[j])
      • 输出 $dp[n]$
  • 正确性证明
    • 最优子结构：$i$ 个苹果的最优解包含 $i-j$ 个苹果的最优解
    • 无后效性：当前决策只依赖于更小规模子问题的解
      本问题中，$dp[i]$ 只依赖于苹果数量 $i$，而不依赖于具体哪几天喂了多少苹果。例如，无论前 $i-j$ 个苹果是如何分配的，$dp[i-j]$ 的值是固定的，因此无后效性成立。
    • 完备性：考虑了所有可能的天数划分方式
  • 复杂度分析
    • 时间复杂度：$O(n\times m)$
    • 空间复杂度：$O(n)$

四、详细实现（从算法到程序）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> A(m + 1);
    for (int i = 1; i <= m; i++) cin >> A[i];

    // 初始化dp数组，dp[i]表示投喂第i个苹果的最大快乐值
    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        // 枚举最后一天喂养的苹果数量j
        for (int j = 1; j <= min(i, m); j++) {
            // 状态转移：前i-j个苹果的最优解加上最后一天喂j个苹果的快乐值
            dp[i] = max(dp[i], dp[i - j] + A[j]);
        }
    }
    cout << dp[n] << endl;

    return 0;
}

五、总结

• 对比本题中贪心和动态规划

  • 贪心策略只考虑“眼前利益”，而忽略了整体组合的效果。就像花钱买东西：如果你总是买最贵的物品，可能钱花完了，但没买到最多实用的东西。喂苹果也是，如果每天喂最多，可能最后几天只剩少量苹果，只能获得低快乐值，而分散喂可能更优。
  • 动态规划：保证正确性，因为它系统性地枚举了所有可能的喂食序列（即所有天数划分方式），通过状态转移确保全局最优。动态规划具有最优子结构和无后效性，能处理任何 $A[i]$ 分布（缺点时复杂度较高）。

  贪心策略失效是因为快乐值 $A[i]$ 可能不按常识增长，局部最优不能保证全局最优。动态规划通过系统比较所有分配方案，确保找到最佳解。

• 这类资源分配问题在以下领域有广泛应用：

  • 投资组合优化
  • 生产计划制定
  • 广告投放策略
  • 计算资源调度