再帰DFSバックパッキングの問題は最適解を求めます.

リュックサックの問題はみんなが知っています.リュックサックの最大の保存量はVで、n個のものを与えられました.

#include
#include
using namespace std;
const int maxn=30;
int n,V,maxValue=0;//n      ，V      
//maxvalue      
int z[maxn],j[maxn];
void DFS(int index,int sumZ,int sumJ){//sumZ sumJ         
	if(index==n){
	if(sumZ<=V&&sumJ>=maxValue)
		maxValue=sumJ;
		return;
}
	//      index   
	DFS(index+1,sumZ,sumJ);
	//     index   
	DFS(index+1,sumZ+z[index],sumJ+j[index]);
}  
int main(){
cin>>n>>V;
for(int i=0;i>z[i];
for(int i=0;i>j[i];
DFS(0,0,0);
cout<

入力:5 8 3 5 1 2 4 1 3出力:10分析:このコードの時間複雑度はn 2で、10000レベル以上の数については許容できません.ここでルームメイトが高強制的に枝を切って最適化できます.動作はDFS関数の品質と価値判断をDFS(index＋1、sumZ＋z［index］、sumJ＋j［index］に移行します.前に、コード時間の複雑さをある程度減らすことができます.
また、同様のテーマは、与えられたn個の整数をk個の数を選択し、k個の数の和をxとし、複数の解法があるならば、選択領域の平方と最大のグループを選択することである.
コードがデバッグされていません.一時保存します.

#include
#include
#include
using namespace std;
int n,k,x,maxpf=0;
vectortem;
vectorans;
void DFS(vector v,int index,int nowx,int nowk,int nowpf){
if(x==nowx&&nowk==k){
	if(nowpf>maxpf){
		maxpf=nowpf;
		ans=tem;
	}
	return;
}
if(index==n||nowk>k||nowx>x) return;
tem.push_back(v[index]);
DFS(v,index+1,nowx+v[index],nowk+1,nowpf+v[index]*v[index]);
tem.pop_back();
DFS(v,index+1,nowx,nowk,nowpf);
}  
int main(){
cin>>n>>k>>x;
vectorv(n);
for(int i=0;i>v[i];
DFS(v,0,0,0,0);
for(int i=0;i

入力:4 2 5 1 2 3出力:1 4