Optimal Crop Selection for Maximum Profit

Crop Profit Maximization
Medium · Dynamic Programming, Knapsack · Various · Hints: Treat buy[i] as knapsack weight and sell[i] - buy[i] as value; for the timed case, ignore crops with days[i] > n.

You are given K crop types, an initial capital money, and a deadline n. Each crop i has three properties:

• buy[i]: the cost to plant it
• sell[i]: the amount received when it is harvested
• days[i]: the number of days it needs to mature

All crops are planted on day 0. You may choose any subset of crop types, and each type may be selected at most once. The total cost of the chosen crops cannot exceed money.

Part 1 has no deadline, so every selected crop eventually matures. Find a subset that maximizes total profit, where profit is sell[i] - buy[i]. Print the sorted 0-based indices of the selected crops. If several subsets achieve the same maximum profit, print the lexicographically smallest sorted index list, comparing index by index; a shorter prefix is smaller. If no crop can be purchased, print -1.

Part 2 adds the rule that every selected crop must mature by day n. Crops with days[i] > n cannot be harvested in time and are excluded. Determine the maximum profit achievable by day n.

The output has two lines: the first line is the answer to Part 1, and the second line is the answer to Part 2.

Example 1:

Input:
4 6 2
4 7 3
3 5 2
5 9 5
2 4 1

Output:
0 3
4

Explanation: Without a deadline, buying crops 0 and 3 costs 6 and earns profit 5; by day 2, only crops 1 and 3 can mature, giving at most profit 4.

Example 2:

Input:
3 5 2
2 5 2
3 4 4
3 5 3

Output:
0 2
3

Explanation: The best unlimited subset is crops 0 and 2 with total profit 5; with deadline 2, only crop 0 can mature, yielding profit 3.

Example 3:

Input:
2 1 10
3 5 1
2 4 1

Output:
-1
0

Explanation: The initial capital 1 is too small to buy any crop, so no profit is possible.

Constraints:

• 1 <= K <= 1000
• 1 <= money <= 10,000
• 1 <= n <= 1000
• 1 <= buy[i] <= 10,000
• 1 <= days[i] <= 1000
• buy[i] < sell[i] <= 20,000
• All values are integers
• Expected time complexity: O(K * money)
• Expected space complexity: O(money)