リュックサック問題のDFS解法

Knapsack Problem
問題の説明:
n個の物品があり、各物品はw[i]、価値はc[i]である.現在、容量Vのリュックサックにいくつかの品物を入れる必要があり、リュックサックに選ばれた品物の総重量がリュックサックの制限重量を超えない場合、リュックサック内の品物の総価値が最大になるようにしなければならない.
DFS解法:
アルゴリズムの考え方:
各アイテムについて、2つのケース(選択、または選択しない)があります.このアイテムを選択するとバックパック内の総重量と総価値量が更新され、それを選択しないと次のアイテムをスキップして判断し、nアイテムを処理した後、このときに記録されたsumWとsumCが選択したアイテムの総品質と総価値である.sumWがVを超えず、sumCがMaxValueよりも大きい場合は、MaxValueを更新します.

#include 
#include 
#include 
#define Maxn 10
using namespace std;

int n,V,MaxValue = 0;//n       ，V      ，MaxValue     
int w[Maxn],c[Maxn];//w[i]        ,c[i]        

void DFS_Kanapsack(int index,int sumW,int sumC)
{
	if(index == n)//    n      
	{
		if(sumW <= V && sumC > MaxValue)
		{
			MaxValue = sumC;//      
		}
		return;
	}
	//
	DFS_Kanapsack(index+1,sumW,sumC);//    index   
	DFS_Kanapsack(index+1,sumW + w[index],sumC + c[index]);//   index   
}

int main()
{
	cin >> n >> V;
	for(int i = 0;i < n;i++)//         
	{
		cin >> w[i];
	}
	for(int i = 0;i < n;i++)//       
	{
		cin >> c[i];
	}
	DFS_Kanapsack(0,0,0);//     0   ，   0，   0;
	cout << MaxValue << endl;

	return 0;
}

各物品には2つの選択があるため、上記のアルゴリズムの時間複雑度は2 n 2^n 2 nであることが容易である.これは明らかに悪い.上記のアルゴリズムでは、n個の物品の選択をすべて確定してから最大価値を更新するが、リュックサックの容量が常にVを超えてはいけないことを無視しているからだ.つまり、選択index物品を上記条件の判断に入れることができ、indexを選択した後、重量がVを超えなければ選択することができる.
改善されたアルゴリズム:

void DFS_Kanapsack(int index,int sumW,int sumC)
{
	if(index == n)
	{
		return;
	}
	DFS_Kanapsack(index+1,sumW,sumC);

	if(sumW + w[index] <= V)
	{
		if(sumC + c[index] > MaxValue)
		{
			MaxValue = sumC + c[index];
		}
		DFS_Kanapsack(index+1,sumW+w[index],sumC+c[index]);
	}
}