Strength Reduction Optimizer

Imagine you're designing a combat system for a game. You need to determine the most efficient way to reduce an enemy's strength using a set of attacks, each with varying damage values and costs. This challenge asks you to write a JavaScript function that finds the optimal combination of attacks to reach a target strength reduction with the minimum total cost.

Problem Description

You are given an array of attack objects, where each object represents an attack with a damage and a cost. You are also given a targetStrength representing the desired strength reduction and a budget representing the maximum allowable cost. Your task is to find the combination of attacks that achieves the targetStrength with the lowest possible cost, staying within the budget.

What needs to be achieved:

• Find the combination of attacks that reduces strength by at least targetStrength.
• Minimize the total cost of the attacks used.
• Ensure the total cost does not exceed the budget.

Key Requirements:

• The function should return an object containing:
  • attacks: An array of the attack objects used in the optimal combination.
  • totalCost: The total cost of the selected attacks.
• If no combination of attacks can achieve the targetStrength within the budget, the function should return null.
• The order of attacks in the attacks array does not matter.

Expected Behavior:

The function should explore different combinations of attacks to find the most cost-effective solution. It should prioritize attacks with high damage-to-cost ratios.

Edge Cases to Consider:

• Empty attack array.
• targetStrength of 0.
• budget of 0.
• targetStrength that cannot be reached within the budget.
• Duplicate attacks in the input array.

Examples

Example 1:

Input:
attacks = [
  { damage: 10, cost: 5 },
  { damage: 5, cost: 2 },
  { damage: 20, cost: 10 }
]
targetStrength = 25
budget = 15
Output:
{
  attacks: [
    { damage: 10, cost: 5 },
    { damage: 10, cost: 5 },
    { damage: 5, cost: 2 }
  ],
  totalCost: 12
}
Explanation: Using two attacks with damage 10 and cost 5, and one attack with damage 5 and cost 2, achieves a strength reduction of 25 (10 + 10 + 5) at a total cost of 12, which is within the budget and optimal.

Example 2:

Input:
attacks = [
  { damage: 10, cost: 5 },
  { damage: 5, cost: 2 }
]
targetStrength = 30
budget = 10
Output:
null
Explanation: No combination of attacks can achieve a strength reduction of 30 within a budget of 10.  Six attacks of damage 5 and cost 2 would reach 30 strength reduction, but the cost would be 12, exceeding the budget.

Example 3: (Edge Case)

Input:
attacks = [
  { damage: 10, cost: 5 }
]
targetStrength = 0
budget = 5
Output:
{
  attacks: [],
  totalCost: 0
}
Explanation:  A target strength of 0 requires no attacks, resulting in a total cost of 0.

Constraints

• attacks will be an array of objects, where each object has damage (integer) and cost (integer) properties.
• targetStrength will be a non-negative integer.
• budget will be a non-negative integer.
• damage and cost will be positive integers.
• The number of attacks in the attacks array can range from 0 to 100.
• Performance: The solution should ideally run within a reasonable time limit (e.g., less than 1 second) for the given constraints.

Notes

• Consider using dynamic programming or a similar optimization technique to efficiently explore the possible combinations of attacks.
• You can assume that the damage and cost values are always positive integers.
• Prioritize minimizing the totalCost while ensuring the targetStrength is met and the budget is not exceeded.
• Think about how to handle cases where multiple combinations achieve the target strength with the same minimum cost. Any valid combination is acceptable in this scenario.