#include<stdio.h> #include<iostream> #include<string> #include<algorithm> #include<cstring> using namespace std; int weight[301], value[301]; int dp[301][301]; int main() { int n, bagweight; memset(dp, 0, sizeof(dp)); cin >> n >> bagweight; for (int i = 0;i < n;i++) { cin >> weight[i] >> value[i]; } for (int j = 0;j <= bagweight;j++) { if (j >= weight[0]) dp[0][j] = value[0]; } for (int i = 1;i < n;i++) { for (int j = 0;j <= bagweight;j++) { if (j < weight[i]) dp[i][j] = dp[i - 1][j]; else { dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); } } } cout << dp[n - 1][bagweight] << endl; } |
Double click to view unformatted code.