โจทย์: มีชุดไอเท็ม แต่ละชิ้นมีค่า values[i] และป้ายกำกับ labels[i] เลือก subset S ที่:
- ขนาด |S| ≤
num_wanted - แต่ละป้ายกำกับ L ใช้ได้สูงสุด
use_limitครั้ง
หาผลรวมค่าสูงสุดที่เป็นไปได้
ตัวอย่าง
values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
Output: 9 (เลือกไอเท็มที่ 1, 3, 5 → 5+3+1=9)
อัลกอริทึม: Greedy + Hash Map
- จับคู่ (value, label) แล้วเรียงลำดับตาม value มากไปน้อย
- เลือกไอเท็มจากค่าสูงสุดลงมา ตรวจสอบข้อจำกัด use_limit ต่อ label
- หยุดเมื่อครบ num_wanted หรือหมดไอเท็ม
ตัวอย่างโค้ด Python
class Solution(object):
def largestValsFromLabels(self, values, labels, num_wanted, use_limit):
# จับคู่และเรียงค่ามากไปน้อย
v = [[values[i], labels[i]] for i in range(len(values))]
v.sort(key=lambda x: x[0], reverse=True)
ans = 0
use = {} # label -> count
i = 0
while num_wanted > 0 and i < len(v):
label = v[i][1]
value = v[i][0]
if label not in use:
# ใช้ label นี้ครั้งแรก
num_wanted -= 1
ans += value
use[label] = 1
elif use[label] < use_limit:
# ใช้ label นี้ยังไม่ครบ limit
num_wanted -= 1
ans += value
use[label] += 1
i += 1
return ans
# ทดสอบ
ob = Solution()
print(ob.largestValsFromLabels([5,4,3,2,1], [1,1,2,2,3], 3, 1)) # Output: 9
ตัวอย่าง Input/Output
Input: [5,4,3,2,1] [1,1,2,2,3] 3 1 Output: 9
ความซับซ้อน: Time O(n log n) จากการเรียงลำดับ, Space O(n)
