问题开始之前， 首先介绍一下利用C++ 头文件<algorithm>中的next_permutation()和pre_permutation产生0， 1， 2， 3，， … N – 1全排列。 这两个函数
产生全排的办法是通过字典序的原理。 next_permutation() 按照递增的办法产生字典序的下一个（唯一确定的， 与当前的排列之间不能夹杂了任何可行的
排列）。 prev_permutation() 产生当前排列的字典序的上一个排列， 是按照递减的顺序。 即产生的字典序比当前排列小的。
下面利用next_permutation产生0, 1, … N – 1 的所有的全排列的方法：
// next_permutation example#include <iostream>// std::cout#include <algorithm> // std::next_permutation, std::sortint main () { int myints[] = {1,2,3}; std::sort (myints,myints+3); // 必须有这一步， 否则可能产生不完全 std::cout << "The 3! possible permutations with 3 elements:\n"; do {std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; } while ( std::next_permutation(myints,myints+3) ); std::cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; return 0;}运行结果如下：
当然也可以采用递归的办法产生， 方法如下：
#include <iostream>using namespace std;void swap(char *fir, char *sec){char temp = *fir;*fir = *sec;*sec = temp;}/* arr is the string, curr is the current index to start permutation from and size is sizeof the arr */void permutation(char * arr, int curr, int size){if(curr == size-1) // base case{for(int a=0; a<size; a++)cout << arr[a] << "\t";cout << endl;}else{for(int i=curr; i<size; i++){swap(&arr[curr], &arr[i]); // 交换permutation(arr, curr+1, size); // 保持curr不变， 对其后面的进行排列swap(&arr[curr], &arr[i]); // 在交换回去}}}int main(){char str[] = "abcd";permutation(str, 0, sizeof(str)-1);return 0;}运行结果：
另外， 从0, ….N 取出其中的K 个数字的所有组合。 利用bitmask数组去mask所有的index， mask掉所有N – K 个元素， 从中取出K个元素。 当然， 我们需要求出所有的拍列（K个1）。
#include <algorithm>#include <iostream>#include <string>using namespace std;// choose K numbers from 0, 1, …, Nvoid comb(int N, int K) {string bitmask(K, 1); // K leading 1'sbitmask.resize(N, 0); // N – K trailing 0's// print all integers and permute bitmaskdo{for(int i = 0; i < N; ++i) { // [0, N – 1] integersif(bitmask[i]) cout << " " << i;}cout << endl;} while(prev_permutation(bitmask.begin(), bitmask.end()));}int main() {comb(5, 3);}
运行结果如下：
最后下面我们说说数组大小为n， 即有n个数， 我们需要从中选出所有可能的组合。 怎么办。 这就是枚举法。 例如我们的n = 4，即我们有四个元素， 所有可能的的组合的数目是2^4 = 16， 即每一个元素都对应选择或者不选这两个可能。 怎么办？？？
这也是 超大背包问题所面临的一个尖锐的问题。事实上， 我们采用的是如下的办法(核心代码)：
for(int i = 0; i < 1 >> n; j++) {for(int j = 0; i < n; ++j) {if(i >> j & 1) {// doing your stuff}}}下面我们对上述代码分析：
n = 4, 那么 1 >> 4 = 16, 即16种可能。 为了直观表示， 改为如下：
for(int i = 0; i < 16; j++) {for(int j = 0; i < n; ++j) {if(i >> j & 1) {// doing your stuff}}}
介绍完了， 言归正传， 下面说说最大背包问题！！
问题描述如下：
有重量和价值分别为（wi, vi）的n个物品。 从这些物品中挑选总重量不超过W的物品。 求挑选方案中总价值和的最大值。
限制条件：
1<= n <= 40,
1<= wi, vi <= 10^(15)
1 <= W <= 10^(15)。
输入：
n = 4
w = {2, 1, 3, 2}
v = {3, 2, 4, 2}
W = 5
输出：
7(挑选0， 1号和3号的物品)。
问题分析：
这个问题是背包问题。 不过这次重量和价值都可以是非常大的数值， 然而相比之下n却是比较小的数值。 使用DP(动态规划)求解背包问题的时间复杂度为
O(nW)， 不太现实。 我们应该利用n比较小的特点求解。 所以我们没有采用动态规划的办法。
挑选物品的方法有2^n种。 所以不能直接枚举。 而是通过将其分成两半之后在枚举！！！！ 这样就满足要求了。
7
拆成两半之后的重量和价值， 每一部分最多只有20个（因为n最大为40）. 我们把前半部分的重量总和和价值总和记为w1， v1。 这样在后半部分寻找总重
w2 < W – w1时， 使得v2最大的选取方法就好了。
当你困难失望的时候，最重要的是事瞧得起你自己；
