SPOJ PARTY

Summary

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 ${\displaystyle A_{ij}}$ = maximum fun we can get from the budget of i and consider only first j party in the list (the solution is clearly ${\displaystyle A_{mn}}$ where m is the given budget and n is the number of parties

${\displaystyle A_{0j}=0\quad \forall j}$

${\displaystyle A_{i0}=0\quad \forall i}$

If ${\displaystyle i then

${\displaystyle A_{ij}=A_{(i)(j-1)}}$

otherwise

${\displaystyle A_{ij}=\max(A_{(i)(j-1)},A_{(i-cost[j])(j-1)}+fun[j])}$

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

• 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

Optimizations here.

Input

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

49 26
48 32


1. Reference 1