DP 백팩 매듭(2)(구조가 완전하고 내용이 간결하며 상태 방정식 편)

//01       
for(int i=1;i<=type;i++){
    for(int j=0;j<=bag;j++){
		if(j>=volume[i]){
			dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume[i]]+value[i]);
		}
		else{
			dp[i][j]=dp[i-1][j];//  
		}
	} 
}
    int maxx=0;
    for(int j=1;j<=bag;j++){
        maxx=max(maxx,dp[type][j]);
    }

//01       
for(int i=1;i<=type;i++){
	for(int j=bag;j>=volume[i];j--){
		dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
	}
}

//         
for(int i=1;i<=type;i++){	
    for(int j=volume[i];j<=bag;j++){
		dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
	}
} 

//    ，    
for(int i=1;i<=type;i++){
	int minn=min(number[i],bag/volume[i]);//  
	for(int k=1;k<=minn;k++){
		for(int j=bag;j>=volume[i];j--){//     ，     
			dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
		}
	}
}

for(int i=1;i<=type;i++){
	for(int j=bag;j>=volume[i];j--){//     ，     
		for(int k=1;k<=number[i]&&(volume[i]*k<=j);k++){//k=0         dp[j]，     0  
			dp[j]=max(dp[j],dp[j-volume[i]*k]+value[i]*k);
		}
	}
    }

//      （    ）     （        ）——    
for(int i=1;i<=type;i++){
    for(int j=volume[i];i<=bag_volume;i++){
        for(int l=weight[i];l<=bag_weight;l++){
            dp[j][l]=max(dp[j][l],dp[j-volume[i]][l-weight[i]]+value[i]);
        }
    }
}

//      （    ） 01  （        ）——    
for(int i=1;i<=type;i++){		
    for(int j=bag_volume;j>=volume[i];j--){
        for(int l=bag_weight;l>=weight[i];l--){
            dp[j][l]=max(dp[j][l],dp[j-volume[i]][l-weight[i]]+value[i]);
        }
    }
}

//  ，number[i]    ，            ，         、             。
for(int i=1;i<=n;i++){
    for(int k=1;k<=number[i];k*=2){
        for(int j=bag;j>=volume[i]*k;j--){
            dp[j]=max(dp[j],dp[j-volume[i]*k]+k);
        }
        number[i]-=k;//!!!
    }
    for(int j=bag;j>=volume[i]*number[i];j--){
        dp[j]=max(dp[j],dp[j-volume[i]*number[i]+number[i]);
    }
}