Solution 4 for Scaler Topics Fortnightly Contest - 10

This article is part of the Scaler Topics Fortnightly Contest - 10

Transform Your Career

Choose from our industry-leading programs designed for career success

NSDC Certified

Modern Software and AI Engineering Program

Master full-stack development with AI integration

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Modern Data Science and ML with specialisation in AI

Advanced data science techniques with AI specialization

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

Advanced AIML with Specialisation in Agentic AI

Deep dive into AIML with focus on Agentic systems

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

DevOps, Cloud & AI Platform Engineering

Build and manage AI-powered cloud infrastructure

12 MonthsDuration

AI-LedCurriculum

Career SupportSupport

+1000 more

Go to Program

NSDC Certified

AI Engineering Advanced Certification by IIT-Roorkee

Premier AI engineering certification from IIT-Roorkee

3 MonthsDuration

AI-LedCurriculum

Career SupportSupport

Go to Program

Solution Approach

• Assuming your’re allowed to chocolates separately only. It is classical knapsack-dp problem.
• Let dp[i][j] be maximum sweetness you can get with j units of money.
• The recurrence relation can be given as-dp[i][j] = max(dp[i-1][j], (dp[i-1][j-B[i]] + A[i] if j >= B[i] else 0))
• Now coming to the original problem: Arrange the chocolates such that chocolates from box are consecutive.
• Whenever you’re on last chocolate of a particular box (say i), update dp[i][j] (for all valid j) if you can take whole box.
• Let box_sweetness[C[i]] is total sweetness of the box of ith chocolate where C[i] is the box of ith chocolate.
• The recurrence relation can be given as-dp[i][j] = max(dp[i][j], (dp[last][j-D[i]] + box_sweetness[C[i]] if j >= D[i] else 0)) where last denotes the first chocolate before i with different box.
• Final ans is dp[N-1][E].

Time Complexity - O(N + M + N * E) Space Complexity - O(N + M + N * E)

C++ Implementation

Java Implementation

Hiring Partners:

GoogleAmazonMicrosoftFlipkartAdobe1200+ more

Python Implementation