01バックパックの問題——DFS/ダイナミックプランニング

質問の概要:
N個の品物とV容量のリュックサックがあります.i番目の品物の価格(すなわち体積、以下同)はw[i]、価値はc[i]である.どのような物品をリュックサックに入れてこれらの物品の費用の総和がリュックサックの容量を超えないようにすることができて、しかも価値の総和が最大で、最大の価値を求めます.(1≤n≤20)
コード1:
(DFS:再帰的遍歴、各アイテムの選択と選択しない2つの結果、すべての状況を遍歴)

#include
using namespace std;
const int maxn=30;

int n,v,maxvalue=0;//     ，    ，     
int w[maxn],c[maxn];//           
void dfs(int index,int sumw,int sumc){//         ，      ，      
	if(index==n){//        n    
		if(sumw<=v&&sumc>maxvalue){
			maxvalue=sumc;//            
		}
		return; //   
	}
	dfs(index+1,sumw,sumc);//   index    
	dfs(index+1,sumw+w[index],sumc+c[index]);//   index    
}

int main()
{
	scanf("%d%d",&n,&v);//          
	for(int i=0;i

コード2:
1、コード1の進化版(計算量の一部を節約した).
2、同じくDFSであるが、現在の総重量がリュックの最大容量を超えた場合、遍歴を継続しない(通称「枝切り」).

#include
using namespace std;
const int maxn=30;

int n,v,maxvalue=0;//     ，    ，    
int w[maxn],c[maxn];//          
void dfs(int index,int sumw,int sumc) //         ，      ，     
{

	if(index==n) //        n    （              ）
	{
		return;
	}

	dfs(index+1,sumw,sumc);//   index    (           ）

	if(sumw+w[index]<=v)
	{
		if(sumc+c[index]>=maxvalue)
		{
			maxvalue=sumc+c[index];//      （           ，       0    ） 
		}
		dfs(index+1,sumw+w[index],sumc+c[index]);//   index   
	}

}

int main()
{
	scanf("%d%d",&n,&v);//         
	for(int i=0; i

コード3:
(動的計画法,時間的複雑度,空間的複雑度ともにO(nV))

#include
#define maxn 1000
using namespace std;

int dp[maxn][maxn];//dp[i][v]   i          v             

int main()
{
	int n,V,w[maxn],c[maxn];//                            
	scanf("%d%d",&n,&V);
	for(int i=0; i

コード4:
(コード3の進化版では,動的計画は1次元配列を用い,空間的複雑度はO(V)に達することができる)

#include
#define maxn 1000
using namespace std;

int dp[maxn];

int main()
{
	int n,V,w[maxn],c[maxn];//                            
	scanf("%d%d",&n,&V);
	for(int i=0; i=w[i]; v--)//         
		{
			dp[v]=max(dp[v],dp[v-w[i]]+c[i]);
		}
	}
	int ans=0 ;
	for(int v=0;v<=V;v++){
		if(dp[v]>ans){
			ans=dp[v];
		}
	} 
	printf("%d
",ans);
	return 0;
}