अरे वहाँ मैं हाल ही में इस प्रश्न पर काम कर रहा हूं लेकिन बैकट्रैकिंग का उपयोग करके इस प्रश्न को हल करने में असमर्थ हूं।

प्रश्न: आपको बैकट्रैकिंग के साथ निम्नलिखित समस्या को हल करना है। आपको 10 धनात्मक पूर्णांक n1, n2, n3, ..., n9, n10 और एक धनात्मक मान K का अनुक्रम दिया गया है।

इस समस्या को हल करने के लिए आपको संख्याओं का क्रमचय a1, a2, a3, ..., a10 प्रिंट करना होगा {0,1,2,3,4,5,6,7,8,9} जैसे कि a1 * n1 + a2 * n2 + a3 *n3 + ... + a10*n10 ≤ K

उपरोक्त विवरण के अनुसार समस्या को हल करने वाले सभी क्रमपरिवर्तनों के बीच, लेक्सिकोग्राफिक रूप से सबसे छोटा प्रिंट करें।

प्रश्न का लिंक

मेरा कोड इस प्रकार है:

#include <algorithm>
#include <iostream>

#define ll long long
#define forn(i,a,b) for(int i = a; i < b; i++)

using namespace std;

ll k;
bool solved = 0; // Tells if we have found a solution or not.
int ans[10];  // Will contain the final sequence of ai s
int arr[10];  // Contains the numbers provided in the question. For this example arr[] = {1,2,3,4,5,6,7,8,9,10}
bool vis[10]={false}; // Denotes if the value ai(see the question) has been used or not

void print();

bool solve(int n, ll sum, int movei)  // n = 10 , movei => which number we have to assign ai to.
{
    if(sum > k) {
            return false;   // Backtrack
    }
    if(movei == n)
    {
        return sum<=k;
    }
    forn(i,movei,n)
    {
        forn(j,0,10)
        {
            if(vis[j]) continue;
            ans[i]=j;
            vis[j]=1;
            if(solve(n, sum + arr[i]*j, movei+1)) return true; // If we found a solution return true
            vis[j]=0;
        }
    }
    return false; // We could not find any solution at all.
}

void print()
{
    forn(i,0,10)
    cout << ans[i] << " ";
}

int main()
{
    int t;         // Number of test cases
    //cin >> t;
    t = 1;
    while(t--)
    {
        forn(i,0,10) arr[i] = i+1; //cin >> arr[i];
        cin >> k;
        if(solve(10,0LL,0)) print();
        else cout << -1;
        cout<<endl;
    }
}

दृष्टिकोण :
१) सभी रास्तों की जाँच करें
2) यदि आप कोई समाधान ढूंढते हैं तो वह शब्दावली की दृष्टि से सबसे छोटा क्रम होगा और इसलिए सत्य लौटता है, जिसका अर्थ है समाधान पाया जाता है
3) समाधान की तलाश जारी रखें।
४) यदि आप किसी भी पथ में समाधान नहीं ढूंढ सकते हैं तो झूठी वापसी करें, अर्थात समाधान नहीं मिल सकता है जिस स्थिति में मैं -1 प्रिंट करता हूं।

मैं इस प्रश्न को कैसे हल कर सकता हूं। मैं वास्तव में इस पर कड़ी मेहनत कर रहा हूं लेकिन कुछ और नहीं सोच सकता।

-4
Michelle 10 जून 2018, 20:46

1 उत्तर

सबसे बढ़िया उत्तर

आपके उत्तरों के लिए @juvian और @PaulMcKenzie को धन्यवाद। कोड इस प्रकार है,

#include <algorithm>
#include <iostream>

using namespace std;

void print(int a[], int n)
{
    for(int i = 0; i < n; i++)
        cout << a[i] << " ";
}

int main()
{
    int test;
    cin >> test;
    int n[10], a[10], k;
    while(test--)
    {
        for(int i = 0; i < 10; i++)
        cin >> n[i];
        cin >> k;

        bool solved = false;

        for(int i = 0; i < 10; i++) a[i] = i;

        do
        {
            int k1 = 0;
            for(int i = 0; i < 10; i++)
            {
                k1 += n[i]*a[i];
            }
            if(k1 <= k)
            {
                solved = true;
                print(a, 10);
                break;
            }
        }while(next_permutation(a, a+10));

        if(!solved) cout << -1;
        cout << endl;
    }
    return 0;
}
0
Michelle 10 जून 2018, 22:12