Welcome Guest.

1Answers

C++ Backtracking method  Is my code not backtracking? Why isn’t it coming out 4 6 or 2 2 6? And still a mistake?

Asked by: Angela Wright 189 views IT January 9, 2019

The topic is a subset of the backtracking method and the problem

Code:

#include<iostream>

using namespace std;

int a[1001];

int b[1001];

int x[1001];

int nsum;

Int n, c;

int k;

 

void subsetsum(int t){

     if( t > n ){

          if(nsum == c){

                k = 1;

                return;

          }

    }

 

    else {

        if(nsum + a[t] <= c) {

              nsum += a[t];

              x[t] = 1;

              subsetsum(t + 1 );

              nsum -= a[t];

        }

    if(nsum + a[t] > c){

           x[t] = 0;

           subsetsum(t+1);

     }

  }

 

}

 

int main(){

cin >> n >> c;

For(int i=1; i<=n; i++){

     cin >> a[i];

     b[i] = a[i];

}

subsetsum(1);

if(k == 1){

     for(int i=1; i<=n; i++){

          if(x[i] == 1 )  cout << b[i] << " ";

     }

}

Else cout < < "No Solution!" << endl;

return 0;

}

1 Answers

  1. +1Votes  

    v[j]=1;backtrack(i+1,total+c[i][j]);v[j]=0;//What does this step mean? The role of v[j] should be to record whether the jth job is assigned. v[j]=0 means that it is not assigned. Your topic is best solved using dynamic programming, see the backpacking question.

    Question: ?
    The topic requirement is to use the backtracking method

    Ward- January 9, 2019 |