# 0-1背包追溯0-1 Knapsack Back Tracking

``bool promissing(int i, int profit, int weight, int n, int w[], int p[], int W, int maxProfit) { int j,k, totweight; double bound;   //if weight is greater than W -> the bag can't hold the item we just took // -> return False if(w[i] >= W) {     return false; } else {     j = i + 1;     bound = p[i];     totweight = w[i];      //Grab as many item as possible (not breaking the bag)     while (j <= n && totweight + w[j] <= W)     {         totweight = totweight + w[j];         bound = bound + p[j];         j++;     }     k = j;     if(k <= n)     {         bound = bound + (W - totweight) * p[k]/w[k]; //grab part of k item that can be fit in the bag      } } return bound > maxProfit; ``

}

``void knapsack_backtracking(int i, int profit, int weight, int n, int p[], int w[], int W, int maxProfit) { //int maxProfit = 0; int bestSet[] = {}; int include[] = {}; int numBest;  //update maxProfit  if (weight <= W && profit > maxProfit) {     maxProfit = profit;     numBest = i;     //bestset = include;     for(int m = 0; m < n; m++)     {         bestSet[m] = include[m];     } }  if(promissing(i, profit ,weight , n , w, p, W, maxProfit)) {     include[i + 1] = 1; //steal item i+1     knapsack_backtracking(i+1, profit + p[i], weight + w[i], n, p, w, W, maxProfit);     include[i + 1] = 0;  //reject item i + 1     knapsack_backtracking(i+1, profit, weight,n,p,w,W, maxProfit); } ``

}