SPOJ PARTY

From Algorithmist
Jump to navigation Jump to search

97 (PARTY) - Party Schedule[edit]

Summary[edit]

This is the classic 0-1 Knapsack problem, which can be handled by dynamic programming. Note that the maximum amount of budget and number of parties are given so that you know the maximum size of dynamic programming array.

Consider = maximum fun we can get from the budget of i and consider only first j party in the list (the solution is clearly where m is the given budget and n is the number of parties

If then

otherwise

First part of the problem is to maximize the amount of fun such that total cost for that fun is less than equal to the party budget.It can be solved using the classical knapsack problem.Now coming to second part where we want to have maximum fun with minimum cost.One observation that i made while solving this problem was that we should find the minimum cost such that we have maximum.

Gotchas[edit]

  • Any points one can easily overlook?
  • The correct way to understand ambiguous formulations?

/*Code*/

  1. include<stdio.h>
  2. define max(A,B) ((A > B) ? A : B)

int main(void) { int i,W,N,j; while(1) { scanf("%d %d",&W,&N); if(W == 0 && N == 0) break; int wt[N+1],val[N+1]; for(i=0;i<N;i++) scanf("%d %d",&wt[i],&val[i]); int K[N+1][W+1]; //Basic Knapsack Problem for(i=0;i<=N;i++) { for(j=0;j<=W;j++) { if(i == 0 || j == 0) K[i][j] = 0; else if(wt[i-1] <= j) K[i][j] = max(val[i-1] + K[i-1][j-wt[i-1]],K[i-1][j]); else K[i][j] = K[i-1][j]; } } //2nd part of the problem where we want to find minimum cost for maximum fun. int best = K[N][W]; for(i=W;i;i--) if(K[N][i]<best) break; printf("%d %d\n",i+1,K[N][W]); } return 0; }

Optimizations[edit]

Optimizations here.

Input[edit]

50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9 

50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2

0 0

Output[edit]

49 26
48 32

Solutions[edit]

F#: SPOJ 97. Party Schedule (PARTY) with F#

References[edit]

  1. Reference 1