ダイナミックプランニング-2 Dリュック(1)


二次元リュックサックは、リュックサックの問題でもあります.
二次元リュックサックの問題は、主にリュックサックが置かれているもので、2つの01リュックサックが1つのテーマに合成されているように、2つの代価が必要です.
引き続き私たちojのテーマの採薬三を持ってきて、リンクを与えます:採薬3
以前に採取した1は2次元配列で,1株は1次元,もう1次元は時間であり,現在は荷重と容積の2つの制限があり,3次元配列c[n][m][t]を採用し,次の株はいずれも1株の同一状態と比較した.荷重と容積をw 1[n]とw 2[n]、価値v[n]に設定します.
表は三次元なので書きにくいので書きません.
式が表示されます.
c[n][m][t] = max(c[n-1][m][t], c[n-1][m-w1[n]][t-w2[n]]+v[n])
これで、上の式に基づいて、2次元配列で私たちのプログラムを書くことができます.
貼り付けコード:
#include 
#define max(a, b) a>b?a:b

int w1[100], w2[100], v[100];
int c[101][101] = {0};

int main(){
	int m, t, n, a;
	scanf("%d %d %d", &m, &t, &n);
	int i, j, k, l;
	for(i=0; i=0; j--)
			for(k=t; k>=0; k--)
				if(j>=w1[i] && k>=w2[i])
					c[j][k] = max(c[j][k], c[j-w1[i]][k-w2[i]]+v[i]);
	printf("%d
", c[m][t]); return 0; }