UVa 11450

From Algorithmist
Jump to navigation Jump to search

11450 - Wedding shopping[edit]

Summary[edit]

Given a money M (<= 200) and a list of garments C (<= 20). Each garment has K (<= 20) models. You want to buy one model for each garment and you want to spend your money as much as possible.

Explanation[edit]

This is a typical Dynamic Programming problem. Let dp(m,c) be the maximum money you can spend when you have m money and you want to buy one model for each garment from garment 0 to garment c-1. If it's not possible to buy one model for each garment then the value of dp(m,c) is -2 (or any other special value).

Then dp(m,c) can be computed recursively:

dp(m,c) =        -2,   if m is negative
                  c,   if c is zero
      max(spending),   otherwise

Where spending is the maximum value of dp(m-ci, c-1) + ci for all the prices of model ci of garment c-1 and dp(m-ci, c-1) is not -2.

The total complexity is O(M*C*max(K)) which is around 200*20*20 = 80,000 operations per test case.

Implementations[edit]

Dynamic Programming can be implemented in a top-down manner or a bottom-up manner.

  • Below is the top-down version (recursion model):
#include <stdio.h>
#include <vector>

using namespace std;

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

vector<int> G[20];
int dp[201][21];

int buy(int m, int c){
  if (m<0) return -2;      // negative money means no solution
  if (c==0) return 0;      // no more garment to buy, this is a solution
  int &ret = dp[m][c];     // ret is an alias of dp[m][c]
  if (ret!=-1) return ret; // if the current state is already visited, return immediately
  ret = -2;                // initialize this state as having no solution (-2)
  REP(i,G[c-1].size()){    // for all model of this garment
    int ci = G[c-1][i];             // the price of model ci of garment c-1
    if (buy(m-ci, c-1) != -2)       // if this model can produce a solution
      ret >?= buy(m-ci, c-1) + ci;  // update the maximum money spent
  }
  return ret;
}

int main(){
  int N,M,C,K;
  scanf("%d",&N);
  while (N--){
    scanf("%d %d",&M,&C);
    REP(i,C){
      scanf("%d",&K);
      G[i].resize(K);                        // resize the vector to size K
      REP(j,K) scanf("%d",&G[i][j]);
    }
    memset(dp,-1,sizeof(dp));
    if (buy(M,C) == -2) puts("no solution"); // -2 means no solution
    else printf("%d\n", buy(M,C));           // this will return the memoized solution
  }
}
  • Below is the bottom-up version:
#include <stdio.h>
#include <vector>

using namespace std;

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)
#define FOR(i,a,b) for (int i=a,_n=b; i<=_n; i++)

vector<int> G[20];
int dp[201][21];

int main(){
  int N,M,C,K;
  scanf("%d",&N);
  while (N--){
    scanf("%d %d",&M,&C);
    REP(i,C){
      scanf("%d",&K);
      G[i].resize(K);                        // resize the vector to size K
      REP(j,K) scanf("%d",&G[i][j]);
    }

    FOR(m,0,M) FOR(c,0,C) dp[m][c] = -2;     // initialize this state as having no solution (-2)

    FOR(m,0,M){
      dp[m][0] = 0;                          // base case solution
      FOR(c,1,C){
        REP(i,G[c-1].size()){
          int ci = G[c-1][i];                // the price of model ci of garment c-1
          if (m>=ci && dp[m-ci][c-1]!=-2)    // if this model can produce a solution
            dp[m][c] >?= dp[m-ci][c-1] + ci; // update the maximum money spent
        }
      }
    }
    if (dp[M][C] == -2) puts("no solution");
    else printf("%d\n", dp[M][C]);
  }
}