読者です 読者をやめる 読者になる 読者になる

AOJ2219 THE BYDOLM@STER

解法
個数制限なしナップサック問題を3パラメータそれぞれについて解く。割と問題文読解ゲー。

配列を再利用すると、0-1ナップサックと個数制限なしナップサックの違いはループの方向のみとなる(蟻本)

という意味を確認しておく。0-1の場合は、j のループが費用の最大 M から w[i] まで回す形にすることで、たった一度のみ品物 i を取ることが出来る。

using namespace std;

int main() {
   
  for(int N, M; cin >> N >> M;) {
    int dp[3][330];
    int w[N];
    int v[N][3];
    for(int i=0; i<N; i++) {
      string s; cin.ignore(); getline(cin, s);
      cin >> w[i] >> v[i][0] >> v[i][1] >> v[i][2];
    }
     
    memset(dp, 0, sizeof dp);
    for(int k=0; k<3; k++)
      for(int i=0; i<N; i++)
        for(int j=w[i]; j<=M; j++)
          dp[k][j] = max(dp[k][j], dp[k][j-w[i]] + v[i][k]);
     
    cout << max(dp[0][M], max(dp[1][M], dp[2][M])) << endl;
  }
   
  return 0;
}