第九章動的計画-1294:Charm Bracelet

1294:Charm Bracelet
時間制限:1000 msメモリ制限:65536 KB提出数:3514通過数:1817【題名説明】クラシック0-1リュック問題、n個の物品があり、番号iの物品の重量はw[i]、価値はc[i]であり、現在、これらの物品の中からいくつかの物品を選んで容量mのリュックサックに入れ、リュックサック内の物体が総重量mを超えない前提でできるだけ価値が大きいようにする.
【入力】1行目:2つの整数、n(物品数、n≦3500)およびm(リュックサック容量、m≦12880).
第2...n+1行::行ごとに2つの整数w[i],c[i]があり、各物品の重量と価値を表す.
【出力】1行、1数のみで、最大総価値を表します.
【入力サンプル】4 6 1 4 2 6 3 12 7【出力サンプル】23【ヒント】No
構想:01リュックサック問題

#include
#include
using namespace std;
int f[20000];
int w[4000];
int c[4000];
int main(){
	int n,m;
	cin >> m >> n;
	int i,j;
	for(i = 1 ; i <= m; i++)
	cin >> w[i] >> c[i];
	for(i = 1; i <= m; i++)
	  for(j = n; j >= w[i];j--)
	  f[j] = max(f[j],f[j-w[i]] + c[i]);//        
	  cout << f[n] << endl;
	return 0;
}