Problem Statement

Given a set of n items, each with a weight and value, and a knapsack with a maximum weight capacityW, the task is to select a subset of items such that:

1. The total weight of the selected items does not exceed the capacity W.
2. The total value of the selected items is maximized.

Variants of the Knapsack Problem:

1. 0/1 Knapsack: You can either take an entire item or leave it, i.e., no fractions.
2. Fractional Knapsack: You can take fractions of items, meaning the items are divisible.

Variant 1: 0/1 Knapsack Problem

Problem Statement:

Given the following arrays:

• values[]: Represents the values (profits) associated with each item.
• weights[]: Represents the weights of each item.
• W: The maximum weight capacity of the knapsack.

The task is to select a subset of items such that:

1. The total weight of the selected items does not exceed W.
2. The total value of the selected items is maximized.

In the 0/1 Knapsack Problem, you cannot take fractional parts of an item. You must either include or exclude each item entirely.

Examples:

Example 1:

Input: values[] = {60, 100, 120}
       weights[] = {10, 20, 30}

W = 50

Output: 160

Explanation:
Calculate the value-to-weight ratios:
  value-to-weight[] = {60/10, 100/20, 120/30}
                    = {6, 5, 4}
Sort the items by their value-to-weight ratios:
  values[] = {120, 100, 60}
  weights[] = {30, 20, 10}
  value-to-weight[] = {4, 5, 6}