南郵OJ 1325サブセットツリー問題

サブセットツリーの問題
時間制限(通常/Java):
1000 MS/3000 MS運行メモリ制限:65536 KByte総提出:11テスト合格:5
試合の説明
キュー分岐限界法を用いてサブセット空間ツリーを探索する関数を設計してみる.この関数のパラメータには,ノード実行可能性判定関数や上界関数などに必要な関数が含まれ,この関数をマウント問題の解に用いる.積載問題は以下の通りである:コンテナiの重量がw iであるn個のコンテナに積載重量cの汽船を積むロットがある.船をできるだけ満タンにする、すなわち、積載体積が制限されない場合に、できるだけ重いコンテナを船に積む、最適な積載案を探し出す.
入力
 
最初の行には2つの正の整数nとcがあります.nはコンテナ数、cは汽船の積載重量である.次の1行にはn個の正の整数があり、コンテナの重量を表す.
しゅつりょく
 
計算した最大積載重量を出力します.
サンプル入力
5 10 7 2 6 5 4
サンプル出力
10
ヒント
 
テーマソース
アルゴリズム設計と実験問題解

#include<iostream>
#define MAX_N 100
#define MAX_C 1000
using namespace std;

int a[MAX_N];
int dp[MAX_N][MAX_C];

int main(){
//	freopen("test.txt","r",stdin);
	int n,c,i,j,temp1,temp2;
	scanf("%d%d",&n,&c);
	for(i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	for(i=1;i<=n;i++){
		for(j=1;j<=c;j++){
			temp1 = dp[i-1][j];
			if(j-a[i]>=0 && temp1<(temp2=a[i]+dp[i-1][j-a[i]])){
				temp1 = temp2;
			}
			dp[i][j] = temp1;
		}
	}
	printf("%d
",dp[n][c]);
}