Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम: 0-1 नैपसैक समस्या हल करना


0-1 नैपसैक समस्या में, आइटम्स का एक सेट दिया जाता है, प्रत्येक का एक वजन और एक वैल्यू होती है। हमें प्रत्येक आइटम की संख्या निर्धारित करने की आवश्यकता होती है जिसे एक संग्रह में शामिल किया जाए ताकि कुल वजन दी गई सीमा से कम या बराबर हो और कुल वैल्यू जितना संभव हो उतना बड़ा हो।

इनपुट

Value = [10, 20, 30, 40, 60, 70]
Weight = [1, 2, 3, 6, 7, 4]
int w = 7

आउटपुट

knapsack value is: 100

एल्गोरिदम

Begin
इनपुट: प्रत्येक का वजन और वैल्यू वाले आइटम्स का सेट
नैपसैक क्षमता सेट करें
आइटम्स की संख्या = sizeof(values) / sizeof(values[0])
Knapsack(Values (ऐरे v में स्टोर्ड), Weights (ऐरे w में स्टोर्ड), अलग-अलग आइटम्स की संख्या (n), नैपसैक क्षमता W)
यदि (w < 0) लौटाएं
यदि कोई आइटम नहीं बचा या क्षमता 0 हो गई तो 0 लौटाएं
वर्तमान आइटम n को नैपसैक में शामिल करें (v[n]) और शेष आइटम्स (n - 1) के लिए घटती क्षमता (W - w[n]) के साथ रिकर्स करें
वर्तमान आइटम n को नैपसैक से बाहर रखें और शेष आइटम्स (n - 1) के लिए रिकर्स करें
वर्तमान आइटम को शामिल या बाहर करके प्राप्त अधिकतम वैल्यू लौटाएं
End

उदाहरण कोड

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

int knapSack(int v[], int w[], int n, int W) {
    if (W < 0)
        return INT_MIN;
    if (n < 0 || W == 0)
        return 0;
    int in = v[n] + knapSack(v, w, n - 1, W - w[n]);
    int ex = knapSack(v, w, n - 1, W);
    return max(in, ex);
}

int main() {
    int v[] = { 10, 20, 30, 40, 60, 70 };
    int w[] = { 1, 2, 3, 6, 7, 4 };
    int W = 7;
    int n = sizeof(v) / sizeof(v[0]);
    cout << "Knapsack value is " << knapSack(v, w, n - 1, W);
    return 0;
}

आउटपुट

Knapsack value is 100

  1. C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम

    इस समस्या में, हमें दो मान दिए गए हैं जो समानांतर चतुर्भुज के आधार (base) और ऊंचाई (height) को दर्शाते हैं। हमारा कार्य C++ में समानांतर चतुर्भुज (Parallelogram) का क्षेत्रफल ज्ञात करने का प्रोग्राम बनाना है।समानांतर चतुर्भुज (Parallelogram) चार भुजाओं वाली एक बंद आकृति है जिसकी विपरीत भुजाएं समान औ

  1. C++ में विग्नेरे सिफर (Vigenere Cipher) का कार्यान्वयन C++ में विग्नेरे सिफर (Vigenere Cipher) का कार्यान्वयन

    विग्नेरे सिफर अल्फाबेटिक टेक्स्ट को एन्क्रिप्ट करने की एक प्रकार की पॉलीअल्फाबेटिक सब्स्टीट्यूशन विधि है। विग्नेरे सिफर टेबल का उपयोग किया जाता है जिसमें A से Z तक के अल्फाबेट्स 26 पंक्तियों में लिखे होते हैं, इस विधि में एन्क्रिप्शन और डिक्रिप्शन के लिए। एन्क्रिप्शन Key: WELCOME Message: Thisis

  1. पायथन प्रोग्राम: 0-1 नैपसैक समस्या पायथन प्रोग्राम: 0-1 नैपसैक समस्या

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें n वस्तुओं के वजन और मूल्य दिए गए हैं, हमें इन वस्तुओं को क्षमता W के बैग में अधिकतम क्षमता w तक रखना है। हमें अधिकतम वस्तुओं को ले जाने की आवश्यकता है और उसका मूल्य वापस करना है। उदाहरण (साधारण दृष्टिकोण) W): return k