C++ প্রোগ্রাম: ফ্র্যাকশনাল ন্যাপস্যাক প্রব্লেম সমাধান

ফ্র্যাকশনাল ন্যাপস্যাক প্রব্লেমে, একটি আইটেম সেট দেওয়া থাকে, প্রতিটির একটি ওয়েট এবং একটি ভ্যালু থাকে। আমাদের আইটেমগুলো ভাঙা দরকার ন্যাপস্যাকের টোটাল ভ্যালু ম্যাক্সিমাইজ করার জন্য এবং এটি লোভীয় (greedy) আপরোচে করা যায়।

অ্যালগরিদম

শুরু
  Item স্ট্রাকচারের একটি অ্যারে নিন
  value, weight, knapsack weight এবং density ডিক্লেয়ার করুন
  প্রতিটি আইটেমের জন্য density=value/weight ক্যালকুলেট করুন
  ডেনসিটি ডিক্রিজিং অর্ডারে আইটেমস অ্যারে সর্ট করুন
  অ্যারেতে টপ থেকে ভ্যালু যোগ করুন টোটাল ভ্যালুতে যতক্ষণ ব্যাগ ফুল নয়, অর্থাৎ total value <= W
শেষ

উদাহরণ কোড

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

typedef struct {
    int v;
    int w;
    float d;
} Item;

void input(Item items[],int sizeOfItems) {
    cout << "Enter total " << sizeOfItems << " item's values and weight" << endl;
    for(int i = 0; i < sizeOfItems; i++) {
        cout << "Enter " << i+1 << " V ";
        cin >> items[i].v;
        cout << "Enter " << i+1 << " W ";
        cin >> items[i].w;
    }
}

void display(Item items[], int sizeOfItems) {
    int i;
    cout << "values: ";
    for(i = 0; i < sizeOfItems; i++) {
        cout << items[i].v << "\t";
    }
    cout << endl << "weight: ";
    for (i = 0; i < sizeOfItems; i++) {
        cout << items[i].w << "\t";
    }
    cout << endl;
}

bool compare(Item i1, Item i2) {
    return (i1.d > i2.d);
}

float knapsack(Item items[], int sizeOfItems, int W) {
    int i, j;
    float totalValue = 0, totalWeight = 0;
    for (i = 0; i < sizeOfItems; i++) {
        items[i].d = (float)items[i].v / items[i].w; // টাইপকাস্টিং (v ইন্ট এবং w ইন্ট তাই d ইন্ট হয়ে যায়)
    }
    sort(items, items+sizeOfItems, compare);
    for(i=0; i> W;
    float mxVal = knapsack(items, 4, W);
    cout << "Max value for " << W << " weight is " << mxVal;
}

আউটপুট

Enter total 4 item's values and weight
Enter 1 V
Enter 1 W
Enter 2 V
Enter 2 W
Enter 3 V
Enter 3 W
Enter 4 V
Enter 4 W
Entered data
values: 2       0       0       0
weight: 0       490642064 0       4196544
Enter Knapsack weight
Total weight in bag 0
Max value for 0 weight is 2