dp-マルチコンストレイントリュックサック

dp-マルチコンストレイントリュックサック
一、テーマの説明
タイトル
N個の品物と1個の容量はVのリュックサックで、リュックサックが耐えられる最大重量はMです.1つの品物は1回しか使えません.体積はvi、重量はmi、価値はwiです.どの品物をリュックサックに入れて、品物の総体積がリュックサックの容量を超えないようにすることができて、総重量はリュックサックの耐えられる最大重量を超えないで、しかも価値の総和は最大です.最大値を出力します.
入力フォーマット
1行目の3つの整数、N,V,Mは、物品点数、リュックの容積、リュックサックが耐えられる最大重量をそれぞれスペースで区切って表しています.次にN行があり、各行の3つの整数vi,mi,wiは、i番目の物品の体積、重量、価値をそれぞれ表すスペースで区切られている.
出力フォーマット
最大値を表す整数を出力します.
入力サンプル
4 5 6 1 2 3 2 4 4 3 4 5 4 5 6
出力サンプル
8
データ範囲
0
二、問題を解く構想
テーマは最適サブ構造の問題であるため,動的計画を用いて行うことができる.
【数学モデリング】
dp[i][j][k]によると、前のiつの物品は、リュックの体積がjであり、リュックが耐えられる重量がkである場合、最も多くの価値を得ることができる.
【状態方程式】
このリュックサックは1つずつしか持てないので、01リュックサックに似たリュックサックの問題と見ることができます.したがって、状態方程式は01リュックサックを参照して書くこともできる:dp[i][j][k]=max(dp[i-1][j][k]、dp[i-1][j-V[i]][k-m[i]]+value[i]);
に注意
jdp[i][j][k]=dp[i-1][j][k]
の原因となる
この状態遷移方程式が得られた理由は以下の通りである.
i番目から考えると、比較して選ぶかしないか.i番目のものを選択すると、リュックサックの体積はこの物体の体積を≧し、リュックサックの重量≧物体の重量であり、最後にこの物体の価値を加える.すなわち、dp[i-1][j-V[i]][k-m[i]+value[i];このリュックサックがリュックサックの体積≧この物体の体積を満たしておらず、リュックサックの重量≧物体の重量であれば、この物品、すなわちdp[i-1][j][k]を放棄する.
【境界(初期化)】
リュックサックの重さやリュックサックの体積、または選択したアイテムの数が0であれば、リュックサックが得る最大の価値は0です.だからリュックサックの境界はdp[i][j][0]=dp[i][0][k]=dp[0][j][k]=0です.
三、時間の複雑さと拡張
時間の複雑さ
三重forサイクルを用いる必要があるため,時間複雑度を大まかに計算できるのがO(nVm)である.
拡張
このリュックサックの制約が2つだけでなく複数あると、時間的複雑度も増加し、空間的複雑度も増加し、最適化戦略はありません.
四、コード

#include
#include
using namespace std;
int n,V,m,dp[110][1010][1010];
struct node{
	int V,m,val;
}A[110];
void init()
{
	scanf("%d%d%d",&n,&V,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&A[i].V,&A[i].m,&A[i].val);
} 
void solve()
{
	for(int i=0;i<=n;i++)//    
	{
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=n;k++)
				if(i==0||j==0||k==0)
					dp[i][j][k]=0;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<A[i].V;j++)//        
			for(int k=1;k<=m;k++)
				dp[i][j][k]=dp[i-1][j][k];
		for(int j=A[i].V;j<=V;j++)
		{
			for(int k=1;k<A[i].m;k++)//            
				dp[i][j][k]=dp[i-1][j][k];
			for(int k=A[i].m;k<=m;k++)
				dp[i][j][k]=max(dp[i-1][j-A[i].V][k-A[i].m]+A[i].val,dp[i-1][j][k]);
		} 
	}
	printf("%d",dp[n][V][m]);
}
int main()
{
	init();
	solve();
	return 0;
}