Task 2 — Multi-Resource Capacity Selection
Objective
Select the best combination of requests that can fit inside a machine with limited resources.
Each request consumes:
CPU
Memory
Storage
and provides a numeric value.
The selected combination must not exceed any capacity.
The goal is to maximize:
TotalValue
Resource Model
A possible model is:
type Resources struct {
CPU int
Memory int
Storage int
}
Request Model
type ResourceRequest struct {
ID string
Resources Resources
Value int
}
Capacity
Use:
CPU Capacity = 16
Memory Capacity = 32
Storage Capacity = 500
Input Requests
R01: CPU=4, Memory=8, Storage=100, Value=35
R02: CPU=6, Memory=12, Storage=150, Value=55
R03: CPU=2, Memory=4, Storage=80, Value=20
R04: CPU=8, Memory=16, Storage=220, Value=70
R05: CPU=4, Memory=6, Storage=120, Value=40
R06: CPU=3, Memory=10, Storage=90, Value=30
R07: CPU=5, Memory=8, Storage=160, Value=48
R08: CPU=1, Memory=2, Storage=40, Value=12
R09: CPU=7, Memory=14, Storage=200, Value=65
R10: CPU=2, Memory=6, Storage=60, Value=25
Required Function
Create a function conceptually equivalent to:
func SelectBestRequests(
requests []ResourceRequest,
capacity Resources,
) SelectionResult
Possible result:
type SelectionResult struct {
Selected []ResourceRequest
UsedResources Resources
TotalValue int
}
Capacity Rules
For the selected requests:
sum CPU <= CPU Capacity
sum Memory <= Memory Capacity
sum Storage <= Storage Capacity
Every constraint must be satisfied simultaneously.
A solution that satisfies CPU but exceeds memory is invalid.
Example
Consider:
R01 + R02 + R05
Resources:
CPU:
4 + 6 + 4 = 14
Memory:
8 + 12 + 6 = 26
Storage:
100 + 150 + 120 = 370
Value:
35 + 55 + 40 = 130
This combination is valid.
The implementation must determine whether another valid combination produces a higher total value.
Important Property
The highest-value requests cannot simply be selected greedily.
For example, one large request may consume enough resources to prevent several smaller requests whose combined value is better.
The solution must evaluate resource trade-offs.
Deterministic Tie-Breaking
If several selections have the same maximum value:
- prefer lower total CPU usage
- then lower total memory usage
- then lower total storage usage
- then lexicographically smaller ordered request IDs
Validation
Reject invalid input where:
request ID is empty
duplicate request ID exists
resource value < 0
request Value < 0
capacity < 0
A request may individually exceed capacity.
Such a request is valid input but can never be selected.
Example:
CPU=32
Memory=4
Storage=20
when CPU capacity is 16.
Empty Selection
The empty selection is valid and has:
TotalValue = 0
This is important if all requests have zero value or none fit.
Additional Test Case
Capacity:
CPU=10
Memory=16
Storage=200
Requests:
A: CPU=6, Memory=8, Storage=100, Value=50
B: CPU=4, Memory=8, Storage=100, Value=45
C: CPU=10, Memory=16, Storage=200, Value=90
Possible results:
A + B = 95
C = 90
Expected selection:
A
B
with:
TotalValue = 95
Optional Extension — Required Requests
Add:
Required bool
to a request.
All required requests must be selected.
If the required set itself exceeds capacity, return an invalid result.
Optional Extension — Priority
Add:
Priority int
and change optimization order to:
maximize total priority
then maximize total value
Goal
This task models a multidimensional capacity-selection problem.
The key challenge is that each request consumes several resources at the same time.
The implementation should distinguish:
resource feasibility
from:
solution quality