C++ Practice [GESP2506 Level 6] Study Group

GESP Level 6 practice, knapsack problem, difficulty General Group.

CCF-GESP C++ Assessment Standards

Hongyang, WeChat Official Account: Hongyang’s Programming Class CCF-GESP C++ Assessment Standards

Comprehensive Guide – [GESP2506 Level 6] Study Group

Problem Requirements

Problem Description

The class teacher plans to divide n students in the class into several study groups, with each student needing to be assigned to one study group. It has been observed that if a study group contains exactly k students, the discussion enthusiasm of that study group is ak.

Given the discussion enthusiasm a1, a2, …, an, please calculate the maximum sum of discussion enthusiasm among all possible ways to divide these n students into study groups.

Input Format

The first line contains a positive integer n, representing the number of students in the class.

The second line contains n non-negative integers a1, a2, …, an, representing the discussion enthusiasm for different group sizes.

Output Format

Output one line, one integer, representing the maximum sum of discussion enthusiasm among all division schemes.

Input and Output Examples

Input #1

1 5 6 3

Output #1

Input #2

0 2 5 6 4 3 3 4

Output #2

Data Range

 For 40% of the test cases, guarantee 1 <= n <= 10. For all test cases, guarantee 1 <= n <= 1000, 0 <= ai <= 1e4.

Problem Analysis

Solution Approach

This is a group optimization problem, which can be solved using dynamic programming. The solution approach is as follows:

Core Problem: Divide n students into several groups, where the size of each group corresponds to different enthusiasm levels, and find the maximum sum of enthusiasm.
Key Observation: This is a variant of the 0/1 knapsack problem.

“Items”: Group sizes (1 to n students)
“Item Values”: Corresponding enthusiasm a[i] for each size
“Knapsack Capacity”: Total number of students n
Each group size can be reused (unlimited supply)

Dynamic Programming Definition:

dp[j]: The maximum sum of enthusiasm that can be obtained by grouping j students
State Transition: dp[j] = max(dp[j], dp[j-i] + a[i-1])
Meaning: Consider using a group of size i to group, the remaining j-i students are grouped optimally

Complexity Analysis:

Time complexity is O(n²)

Space complexity is O(n)

Example Code

#include <bits/stdc++.h>using namespace std;int n;int main(){    cin >> n;  // Input total number of students    vector<int> a(n);  // Store enthusiasm for different group sizes    for (int i = 0; i < n; ++i) {        cin >> a[i];  // Input a1, a2, ..., an    }        vector<int> dp(n + 1);  // dp array, dp[j] represents the maximum enthusiasm for j students        // Dynamic programming process - complete knapsack idea    for (int i = 1; i <= n; ++i) {  // i represents the current group size        for (int j = i; j <= n; ++j) {  // j represents the current number of students            // State transition: compare not forming this group size vs forming a group of size i            dp[j] = max(dp[j], dp[j - i] + a[i - 1]);        }    }        cout << dp[n] << endl;  // Output the maximum enthusiasm for n students    return 0;}

“Comprehensive Guide–” series problems can be evaluated online at Informatics Olympiad Comprehensive Guide (C++ Version).