Submission #1531189

---

Source Code Expand

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;

#define REP(i,n) for(int i=0;(i)<(n);(i)++)

int dp[102][10004];

int knapsack(int N, int W, int v[], int w[]) {
	//int dp[102][10004];
	REP(i, N + 1) {
		REP(j, W + 1) dp[i][j] = -1;//初期化
	}

	REP(i, N + 1) dp[i][0] = 0; //ナップザックの大きさが0なら価値の最大は0
	REP(j, W + 1) dp[0][j] = 0; //品物の数が0なら価値の最大は0


	int dia, top;
	for (int i = 1;i <= N;i++) {
		for (int j = 1;j <= W;j++) {
			if (j - w[i] >= 0) dia = dp[i - 1][j - w[i]] + v[i];//i番目の品物を選んだ時
			else dia = 0;
			top = dp[i - 1][j];//i番目の品物を選ばなかったとき
			dp[i][j] = max(dia, top);
		}
	}

	return dp[N][W];
}

int main() {
	int N, W;
	cin >> N >> W;

	int v[102], w[102];
	for (int i = 1; i <= N; i++) {//1-origin
		cin >> w[i] >> v[i];
	}


	int ans = knapsack(N, W, v, w);

	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result