CCF CSP 第37次（2025.03）（2_机器人饲养指南_C++）

CCF CSP 第37次（2025.03）（2_机器人饲养指南_C++）

• • • 解题思路：
    • • 思路一（完全背包）：
    • 代码实现
    • • 代码实现（思路一（完全背包））：

时间限制： 1.0 秒
空间限制： 512 MiB
原题链接

解题思路：

思路一（完全背包）：

1、解题步骤拆分：
① 数据输入：

• 第一行输入 n m（int）。
• 第二行输入 m 个整数 A1, A2, …, Am 代表一天内投喂不同苹果数的收益。

② 数据处理：通过分析此次题目是一个完全背包问题：

• 每天投喂苹果的数量是物品的重量。
• 投喂苹果后获得的快乐值是物品的价值。
• 整数n代表苹果总数，也就是背包容量。
• 整数m代表含有m种投喂方式（也即m种物品）。
• dp[i] 代表容量为 i 时背包能够获得的最大价值。
• 状态转移方程：dp[i] = max(dp[i], dp[i - j] + value[j])。
• dp[0] = 0，背包容量为 0 时能放的最大价值是 0。
• 因为相同物品可以重复使用，所以内层循环应从当前物品位置开始遍历，即遍历顺序为从左到右。

③ 数据输出：最终 dp[n] 即为容量为 n 时能获得的最大价值。

代码实现

代码实现（思路一（完全背包））：

#include<iostream>
#include<vector>
// #include<bits/stdc++.h>   // 引入所有标准库，一般不推荐使用，可能导致不必要的头文件引入
using namespace std;

int main(int argc, char const *argv[])
{
    int n, m;
    // 输入总苹果数（背包容量）n 和 投喂方式数量 m
    cin >> n >> m;
    
    vector<int> A(m);
    // 输入m个整数，代表每种投喂方式对应的收益(物品的重量为i+1,价值为A[i])
    for (int i = 0; i < m; i++){
        cin >> A[i];
    }
    
    // 创建 dp 数组，初始化为 0， dp[i] 代表容量为 i 时的最大价值
    vector<int> dp(n + 1, 0);

    // 遍历每个投喂方式(物品)
    for (int i = 0; i < m; i++){
        // 遍历容量，从当前投喂方式的数量开始，直到容量为 n
        // 这里 i+1 表示的是当前投喂方式对应的苹果数，因为 A[i] 代表每种方式的收益（苹果数）
        for (int j = i + 1; j <= n; j++){
            // 计算在当前容量下能获得的最大价值
            dp[j] = max(dp[j], dp[j - (i + 1)] + A[i]);
        }
    }
    
    // 输出最大值，即 dp[n]，代表容量为 n 时的最大快乐值
    cout << dp[n] << endl;
    
    return 0;
}

欢迎大家和我沟通交流(✿◠‿◠)