P1757 Tongtian: Group Knapsack

Direct to the Skyroad · Xiao A's Adventure II.

After the $01$ knapsack came out, Xiao A became very interested. One day, Xiao A went on a trip and found that his backpack was different from the $01$ knapsack. His items can be roughly divided into $k$ groups, and items within the same group are mutually exclusive (you may choose at most one item from each group). Now he wants to know the maximum total value he can obtain.

Two integers $m,n$, indicating there are $n$ items in total, and the backpack can bear a maximum weight of $m$. Then $n$ lines follow. Each line contains 3 integers $a_i,b_i,c_i$, representing the item's weight, value, and group index.

One integer: the maximum total value.

$0 \leq m \leq 1000$, $1 \leq n \leq 1000$, $1\leq k\leq 100$, $a_i, b_i, c_i$ are within the `int` range. Translated by ChatGPT 5