24

// Problem      : 0-1 Knapshack with solution print
int cost[100];
int weight[100];
int dp[100][1000];
int dir[100][1000];
int KnapShack(int i, int w) {
	if (i == n+1)
		return 0;
	int &ret = dp[i][w];
	if (ret != -1)
		return ret;
	int profit1 = 0;
	int profit2 = 0;
	if (w + weight[i] <= cap)
		profit1 = cost[i] + KnapShack(i+1, w + weight[i]);
	else
		profit1 = 0;
	profit2 = KnapShack(i+1, w);
	if (profit1 > profit2) {
		dir[i][w] = 1;
		return ret = profit1;
	}
	else {
		dir[i][w] = 2;
		return ret = profit2;
	}
}
void printSol(int i, int w) {
//	 base case
	if (i == n+1)
		return;
//  or
//	if (dir[i][w] == -1)
//		return;
	if (dir[i][w] == 1) {
		cout << i << " -> " << cost[i] << endl;
		printSol(i+1, w+weight[i]);
	}
	else {
		printSol(i+1, w);
	}
}

// Call : KnapShack(1, 0)

// Bit Mask
int count_one(int mask)  { return __builtin_popcount(mask); }
int Set(int N,int pos)   { return N=N | (1<<pos); }
int reset(int N,int pos) { return N= N & ~(1<<pos); }
bool check(int N,int pos){ return (bool)(N & (1<<pos)); }