Note: This problem isn't a DP problem, but a greedy problem. However, it provides a good introduction to the concept of knapsack problems.

Contents

1. Problem Statement
2. Algorithm
3. Example
4. Steps
5. Source Code
6. Code BreakDown
7. Handwritten Notes

• You're a thief trying to steal items from a general store.
• Each item has a weight and a profit associated with it.
• You have a bag with a specific weight capacity.
• You want to maximize your profit by filling the bag with items, considering their weights and profits.
• You can take fractional parts of items if necessary.
• You will put the item in the bag only if item's weight <= capacity.
• In case the item's weight > capacity, then we will only carry the fractional part of the item that can be accommodated in the bag.

1. Sort the items based on their value per unit weight (profit divided by weight).
2. Greedily select items to fill the bag until it's full.

The Item class can be created as:

class Item
{
    public:
    int weight;
    int value;
    //constructor
    Item(int weight, int value)
    {
        this->weight = weight;
        this->value = value;
    }
}

Each item is stored as {weight,profit}

Item arr[] = {{1,20},{2,30},{3,50},{4,30}};
capacity = 5

Output : 85

Now, the Items will be sorted as {A,C,B,D}

Assuming that he's carrying a bag with capacity 5 then:

Output : 85

• In the above table:
  • If arr[i].weight <= capacity:
    • finalProfit += arr[i].value; // The profit will be added
    • capacity -= arr[i].weight; // The capacity of the sack will be shrunk
  • Else arr[i].weight > capacity:
    • finalProfit = finalProfit + arr[i].value * (capacity/arr[i].weight);
    • break;

#include <iostream>
#include <algorithm>
using namespace std;

class Item {
public:
    int weight;
    int value;

    Item(int weight, int value) {
        this->weight = weight;
        this->value = value;
    }
};

bool compare(Item a, Item b) {
    return (a.value / a.weight) > (b.value / b.weight);
}

double KnapSack(Item arr[], int N, int capacity) {
    sort(arr, arr + N, compare);

    double maxProfit = 0.00;
    for (int i = 0; i < N; i++) {
        if (arr[i].weight <= capacity) {
            capacity -= arr[i].weight;
            maxProfit += arr[i].value;
        } else {
            maxProfit += arr[i].value * (double(capacity) / arr[i].weight);
            break; // No need to process further items after using fractional part
        }
    }

    return maxProfit;
}

int main() {
    Item arr[] = {{1, 20}, {2, 30}, {3, 50}, {4, 30}};
    int N = sizeof(arr) / sizeof(arr[0]);
    int capacity;
    cout << "Enter the capacity of KnapSack : ";
    cin >> capacity;
    cout << "The maxProfit our KnapSack can have is : " << KnapSack(arr, N, capacity) << endl;
    return 0;
}

Reading someone else's code can be tricky, but chill out! This series will explain things step-by-step, making every part crystal clear.

Include Part

#include <iostream>
#include <algorithm>
using namespace std;

• here the #include <algorithm> is used to call the sort function

Main Part(Driver Code)

int main() {
    Item arr[] = {{1, 20}, {2, 30}, {3, 50}, {4, 30}};
    int N = sizeof(arr) / sizeof(arr[0]);
    int capacity;
    cout << "Enter the capacity of KnapSack : ";
    cin >> capacity;
    cout << "The maxProfit our KnapSack can have is : " << KnapSack(arr, N, capacity) << endl;
    return 0;
}

• here the N is used to find the total size of the array

  •   // This code demonstrates how to calculate the size of arrays in C.
      int integer_array[] = {1, 2, 3, 4, 5}; 
      int integer_array_size_in_bytes = sizeof(integer_array); // Calculate the total size of the integer array in bytes (4*5 = 20)
      int integer_element_size = sizeof(integer_array[0]);  // Determine the size of a single integer element in bytes. (4)
      int integer_array_element_count = integer_array_size_in_bytes / integer_element_size; // Calculate the number of elements in the integer array (20/4 = 5)
    
      // The same logic applies to a character array:
      char char_array[] = {'a', 'b', 'c'}; //1*3 = 3
      int char_size = sizeof(char_array)/sizeof(char_array[0]); //3/1 = 3
    
    

Fractional KnapSack Code

bool compare(Item a, Item b) {
    return (a.value / a.weight) > (b.value / b.weight);
}

double KnapSack(Item arr[], int N, int capacity) {
    sort(arr, arr + N, compare);

    double maxProfit = 0.00;
    for (int i = 0; i < N; i++) {
        if (arr[i].weight <= capacity) {
            capacity -= arr[i].weight;
            maxProfit += arr[i].value;
        } else {
            maxProfit += arr[i].value * (double(capacity) / arr[i].weight);
            break; // No need to process further items after using fractional part
        }
    }

    return maxProfit;
}

• Here the sort(arr, arr + N, compare); function is being used to sort the elements
  • It uses the sort function from the Standard Template Library.
  • arr : This is the starting address of the array that needs to be sorted.
  • arr + N : This expression indicates the end of the range to be sorted.
  • compare : It's a custom comparator
    • It's taking two elements as arguments Item a Item b and sorting them based on their value per unit weight (profit divided by weight).
    • It will return a boolean value that will decide how the array will be sorted.
    • return (a.value / a.weight) > (b.value / b.weight) means array will be sorted in the descending order.
• maxProfit += arr[i].value * (double(capacity) / arr[i].weight); : here the double(capacity) is being type casted into double
  • capacity is an integer, and directly dividing it by arr[i].weight (also an integer) would result in integer division, truncating the result and potentially neglecting a remaining fraction of capacity.

Happy Coding!