给出一个序列，枚举这个序列的所有子序列（可以不连续） 例如序列{1,2，3}来说 他的所有子序列为{1}、{2}、{3}、{1,2}、{1,3}、{2,3}、{1,2，3} 枚举所有子序列的目的很明显：可以从中选择一个“最优”子序列，使它的某个特征是所有子序列中最优的， 如果有需要，还可以把这个最优子序列保存下来。 显然这个问题也等价于枚举从N个整数中选择K个数的所有方案
给定N个整数，从中选择K个数，使的这K个数之和恰好等于一个给定的整数X 如果有多种方案，选择他们元素平方和最大的一个，保证方案唯一 从4个整数{2,3，4,4}选择2个数， 使他们的和为6 显然有{2,4}{3，3,}两个方案，其中平方和最大的方案是{2,4}
与之前的问题类似 我们需要记录当前处理的整数编号index 由于恰好选择K个数，因此需要一个参数nowK来记录当前已经选择的数的个数 另外，还需要参数sum来记录整数之和 sumSqu记录当前已选平方和 此处，讲解如何保存最优方案（平方和最大的方案） 1.temp数组，用来存放当前已经选择的整数， 这样当试图进入“index号数”这条分支时，就可以把A[index]放入temp中 而当这条分支结束时，就把他从temp中取出，使他不会影响“不选index号数”这条分支。 2.如果，在某个时候，发现当前已经选择了k个数，且这k个数之和恰好为x时，就去判断平方和是否比已有的最大平方和maxSumSqu还要大：如果确实更大，那么说找到了更优的方案，把temp赋值给存放最优方案的数组ans 3.这样，当所有方案都枚举完毕，ans存放的就是最优方案，maxSumSqu存放的就是对应的最优值
int n,k,x,maxSumSqu=-1,A[maxn]; vector<int>temp,ans; void dfs(int index,int nowK,int sum,int sumSqu){ if(nowK==k&&sum==x){ if(sumSqu>maxSqu){ maxSumSqu=sumSqu; ans=temp; } return; } if(index == x || nowK>k||sum>x)return; temp.push(A[index]); dfs(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]); temp.pop_back(); dfs(index+1,nowK,sum,sumSqu); } //如果每个整数可以被选择多次，就当选择了index号数，不应当直接进入index+1号数的处理 //显然，还应该继续选择index号数，直到某个时候不再选择index号数，就会通过“不选index号数”这条分支进入index+1号数的处理 //将选择“index号数”的这条分支代码 dfs(index+1,nowK+1,sum+A[index],sumSqu+A[index]*A[index]); //修改为 dfs(index,nowK+1,sum+A[index],sumSqu+A[index]*A[index]); //背包问题 //有n件物品，每件物品的重量为w[i]，价值为c[i]，现在需要选出若干物品来放入一个容量为v的背包中 //使的在选入背包的物品重量和不超过容量v的前提下，让背包中物品的价值和最大，求最大价值(1<=n<=20) //5 8 //3 5 1 2 2 //4 5 2 1 3 //5 8 //3 5 1 2 2 //4 5 2 1 3 //10 #include <iostream> #include <cstdio> using namespace std; int n,v; int w[30],c[30]; int maxValue=0; void dfs(int index,int sumW,int sumC){ if(index==n){ return; } if(sumW<=v&&sumC>maxValue){ maxValue=sumC; } //if(index>n||sumW>v)return; dfs(index+1,sumW,sumC);//不选第index件物品 dfs(index+1,sumW+w[index],sumC+c[index]);//选第index件物品 } int main() { scanf("%d%d",&n,&v);//5 8 //5件物品，背包容量为8 for(int i=0;i<n;i++){ scanf("%d",&w[i]);//3 5 1 2 2//每件物品的重量 } for(int i=0;i<n;i++){ scanf("%d",&c[i]);//4 5 2 1 4//每件物品的价值 } dfs(0,0,0);//第0件物品---w[0]---c[0],初始化为第0件物品，当前总重量和总价值均为0 printf("%d\n",maxValue); return 0; }