Resource Allocation Dynamic Programming | Dataford Interview Questions

PhonePe wants to distribute a fixed promotional budget across merchants. For each merchant, several campaign options are available, where each option has a spending cost and an expected business value. Select at most one option per merchant and maximize the total expected value without exceeding the budget.

Formal Specification

Implement allocate_campaign_budget(budget, merchant_options), where budget is an integer and merchant_options[i] is a list of [cost, value] pairs for merchant i. The function must return the maximum total value achievable. A merchant may receive no campaign, and unused budget is allowed.

Constraints

0 <= budget <= 10^4
1 <= len(merchant_options) <= 100
Each merchant has at most 20 options
0 <= cost <= budget
0 <= value <= 10^6
Each option is represented as [cost, value]
At most one option may be selected for each merchant

Function Signature

def allocate_campaign_budget(budget, merchant_options):

Your question is Resource Allocation Dynamic Programming. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Formal Specification

Constraints

0 <= budget <= 10^4
1 <= len(merchant_options) <= 100
Each merchant has at most 20 options
0 <= cost <= budget
0 <= value <= 10^6
Each option is represented as [cost, value]
At most one option may be selected for each merchant

Function Signature

def allocate_campaign_budget(budget, merchant_options):

Your question is Resource Allocation Dynamic Programming. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.