AOJ_0042
ナップサック問題とくだけ。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 1000; const int MAX_W = 1000; int W, N; int w[MAX_N + 1], v[MAX_N + 1]; int dp[MAX_N + 1][MAX_W + 1]; /* dp[i][j] := i番目までの品物を重さj以下となるように選んだときの最大の価値 dp[0][j] := 0 dp[i][j] := max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); */ int res; int solve(){ for(int i = 0; i <= W; i++) dp[0][i] = 0; for(int i = 1; i <= N; i++){ for(int j = 0; j <= W; j++){ if(0 > j - w[i]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } } int ans = dp[N][W]; res = W; for(int i = 1; i <= N; i++) for(int j = 0; j <= W; j++) if(dp[i][j] == ans) res = min(res, j); return ans; } int main(){ int count = 1; while(scanf("%d", &W)){ if(W == 0) return 0; printf("Case %d:\n", count); scanf("%d", &N); for(int i = 1; i <= N; i++){ scanf("%d, %d", &v[i], &w[i]); } printf("%d\n", solve()); printf("%d\n", res); count++; } return 0; }