Pの競プロ記

競技プログラミングに関することを書きます。

AOJ 1092 Make KND So Fat

概要


問題文はこちら
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1092


解法


動的計画法(DP)で解くことができます。

この問題では2回動的計画法をします。(1回の動的計画法だけでも解を求めることはできるかもしれませんが、私は2回に分けてやりましたし、たぶんそのほうが分かりやすいのではないでしょうか。)

まず1回目、下準備的なものです。
int buy[甘味セットの種類][今持っているお金] ⇒ その時の最大の満足度
これを求めます。典型的なナップサック問題なので分からない人はググればすぐにでてくると思います。

そして2回目、求めたい解を求めていきます。
int dp[日数][今持っているお金] ⇒ その時の最大の満足度
これを求めます。私の書いたコードだと少し分かりづらいかもしれませんが、これで求めることができます。


余談ですが「2回動的計画法をする」という発想があまり浮かばないような気がします。


ソースコード

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<complex>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<cassert>
#include<cstring>
using namespace std;
 
#define REP(i,x,n) for(int i = x ; i < (int)(n) ; i++)
#define rep(i,n) REP(i,0,n)
#define f first
#define s second
#define mp make_pair
#define pb push_back
 
typedef pair<int,int> P;
typedef long long ll;
 
static const int INF = (1 << 29);
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
 
int s,d,m;
vector<int> w[100],p[100];
int f[100];
int buy[100][301];
int dp[101][301];
int tmp[301];
 
int solve(){
  memset(buy,-1,sizeof(buy));
  memset(dp,-1,sizeof(dp));
  dp[0][m] = 0;
   
  for(int i = 0; i < s; i++){
    buy[i][m] = 0;
    int sz = w[i].size();
    for(int j = 0; j < sz; j++){
      memset(tmp,-1,sizeof(tmp));
      for(int k = m; k >= 0; k--){
        if(buy[i][k] == -1) continue;
        if(k < p[i][j]) continue;
        tmp[k - p[i][j]] = max(tmp[k - p[i][j]], buy[i][k] + w[i][j]);
      }
      for(int k = m; k >= 0; k--){
        buy[i][k] = max(buy[i][k], tmp[k]);
      }
    }
  }
   
  for(int i = 0; i < d; i++){
    for(int j = m; j >= 0; j--){
      if(dp[i][j] == -1) continue;
      for(int k = m; k >= 0; k--){
        int useMoney = m - k;
        if(j - useMoney < 0) break;
        if(buy[f[i]][k] == -1) continue;
        dp[i + 1][j - useMoney] = max(dp[i + 1][j - useMoney], dp[i][j] + buy[f[i]][k]);
      }
    }
  }
  
  int satisfy = 0;
  int money = 0;
  for(int j = 0; j <= m; j++){
    if(satisfy <= dp[d][j]) {
      satisfy = dp[d][j];
      money = m - j;
    }
  }
   
  cout << satisfy << " " << money << endl;
}
 
int main(){
  while(cin >> s >> d >> m){
    rep(i,100){
      w[i].clear();
      p[i].clear();
    }
    rep(i,s){
      int k;
      cin >> k;
      rep(j,k){
        int W,P;
        cin >> W >> P;
        w[i].push_back(W);
        p[i].push_back(P);
      }
    }
    rep(i,d) cin >> f[i];
    solve();
  }
  return 0;
}