Problem 17: Knapsacks and Boss Battles
I was browsing through my old Hackerrank account when I found this interesting problems dealing with arrays. I just reframed the problem statement to make it look more interesting:
Let us assume a situation where you are caught in a boss battle in a video game. The boss health is given by an integer ‘k’ and you have ‘n’ weapons each having its own damage ability (basically, an array of ‘n’ damage points). You can perfectly defeat the monster if you manage to bring its health down to zero (exactly) using your weapon array. A perfect defeat is rewarded with a rare item that guarantees character upgrade.
Now, you want to know whether you can get this rare item or not given that you have infinite time and stamina to strike as many times as you want with any combination of weapon(s).
Let us get the rare item !
Note that we have some constraints here : 1 <= n,k <= 2000 and no weapon is associated with damage points over 2000 and less than 1.
Solution
We shall make use of Dynamic Programming (s). This is a solution methodology that is often covered in Data Structures and Algorithms courses. In simple terms, this method makes clever use of the solution of subproblems to build up the solution up to the required level.
For starters, we can quickly define an array called ‘w’ which will store the ith weapon’s damage points in w[i] (ith index of the array). Now how do we make use of s here?
Note that the least damage point is 1 and the maximum value of the boss health is 2000. Therefore, we wouldn’t be using any weapon more than 2000 times.
It turns out that the best way to think of the subproblems is this case is to calculate the sum of any combination (with repeats and rejects) of first ‘i’ elements of ‘w’ which is closest to ‘j’. This sum can be stored in a 2-D matrix (s) at s[i][j].
Base cases :
For i = 0 or j = 0 we know that s[i][j] will be equal to 0 simply because we cannot have a nonzero sum with
zero elements and that each sum is non-negative.
Build up:
If we know the sum considering first ‘i-1’ weapons which is closest to ‘j’ (i.e. an infimum) or s[i-1][j] and the sum considering the first ‘i’ weapons upto ‘j-w[i]’, we can move up the ladder by computing:
s[i][j] = max(s[i-1][j], s[i][j-w[i]] + w[i])
The assignment above makes sense because if we add the ith weapon to our move sequence then we get to deal a damage of w[i] that gets added to the old sum for ‘i’ weapons i.e. s[i][j-w[i]]. We use the max operator to ensure that we obtain the sum that is closest to ‘j’.
There is one case that is missing here- What if j < w[i]? - In that case, it is even simpler. Since j < w[i], we cannot add benefit by adding the ith weapon to the move list. Therefore in this case:
s[i][j] = s[i-1][j]
We can build this matrix for each i and j each starting from 1 to n. The answer is simply obtained by checking if s[n][k] i.e. the closest sum to ‘k’ using the whole array of weapons of size ‘n’ is equal to ‘k’ or not.
Implementation with C++ code
I am adding the code for this below:
// add common header files
int w[2001]; // weapon array
int s[2001][2001]; // sum array
int main()
{
scanf("%d %d",&n,&k); // user input n and k
for (int i=1;i<=n;i++)
scanf("%d",&w[i]); // build up weapon damange pts array
for (int i=0;i<=2000;i++)
s[0][i] = s[i][0] = 0; // base case for s
for (int i=1;i<=n;i++)
for (int j=1;j<=k;j++)
if (j >= w[i])
s[i][j] = max(s[i-1][j], s[i][j-w[i]] + w[i]);
else
s[i][j] = s[i-1][j];
if (s[n][k] == k)
{
printf("Rare item possible");
}
else
{
printf("Not possible");
}
return 0;
}