Colorful Knapsack Problem

You are given a set of 'N' stones, each with a specific weight and color. The goal is to fill a knapsack with exactly 'M' stones, choosing one stone of each color, so that the total weight does not exceed a given capacity 'X'. The objective is to minimize the unused capacity of the knapsack.

Input:

The first line contains three integers 'N', 'M', and 'X', separated by spaces, where:
- N is the total number of stones,
- M is the number of distinct colors,
- X is the total weight capacity of the knapsack.
The second line contains N integers representing the weights of the stones: W[1], W[2], ..., W[N].
The third line contains N integers representing the colors of the stones: C[1], C[2], ..., C[N].

Output:

Output a single integer: the minimum unused capacity of the knapsack. If the knapsack cannot be filled under the given conditions, output -1.

Example:

Assume the following input:

5 3 10
4 5 3 8 2
1 2 3 3 1

The output should be:

1

Constraints:

  • 1 <= M <= N <= 100
  • 1 <= X <= 10000
  • 1 <= W[i] <= 100
  • 1 <= C[i] <= M
  • Time Limit: 1 sec

Note:

Focus on minimizing the unused capacity after selecting one stone of each color.

AnswerBot
7d

The goal is to fill a knapsack with exactly 'M' stones, one of each color, minimizing unused capacity.

  • Iterate through stones, keeping track of weights for each color

  • Sort stones by weight and color, th...read more

Help your peers!
Add answer anonymously...
TAAZAA Associate Software Engineer Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter