Perhaps its not necessary to run all the loops. There may be some ranges to look for the optimum within.
BTW are you going to take part in Sunday's contest or not?
I wrote you several messages, but you keep silence.
![:evil:](./images/smilies/icon_evil.gif)
Moderator: Board moderators
Code: Select all
2 1
14 4
16 2
24 20
11 15
8 5
11 10
17 5
17 2
9 17
3 16
2 3
16 4
13 2
6 1
7 20
15 13
12 1
13 8
8 10
17 15
7 7
18 3
10 17
14 5
3 1
19 7
7 19
8 3
1 8
18 1
10 14
1 5
2 6
10 19
1 1
7 8
26 20
16 1
20 20
2 5
16 9
11 14
7 14
4 14
6 9
20 6
12 11
5 9
8 5
16 12
3 18
6 2
4 14
17 14
2 4
15 2
1 3
12 14
16 18
17 14
7 3
2 16
20 19
14 9
10 12
9 4
10 18
16 19
18 19
6 13
15 14
12 6
5 11
6 7
13 20
3 17
18 19
2 15
0 0
titid_gede wrote:can you provide me outputs for this following inputs :
...
thanks![]()
-titid-
Code: Select all
Jury #1
Best jury has value 14 for prosecution and value 4 for defence:
1
Jury #2
Best jury has value 195 for prosecution and value 192 for defence:
1 2 3 6 7 8 10 11 12 13 14 15 16 17 18 20 21 22 23 24
Jury #3
Best jury has value 29 for prosecution and value 28 for defence:
1 2 6
Jury #4
Best jury has value 237 for prosecution and value 237 for defence:
1 2 4 5 6 7 9 10 13 14 16 17 18 19 21 22 23 24 25 26
Jury #5
Best jury has value 109 for prosecution and value 111 for defence:
1 2 4 5 7 8 9 10 13
horape@elanor:~/acm$ tail 323.out
1 2 6
Jury #4
Best jury has value 237 for prosecution and value 237 for defence:
1 2 4 5 6 7 9 10 13 14 16 17 18 19 21 22 23 24 25 26
Jury #5
Best jury has value 109 for prosecution and value 111 for defence:
1 2 4 5 7 8 9 10 13
Code: Select all
#include <stdio.h>
#define MOD(a) ((a)>=0?(a):(-(a)))
#define MAXN 200+10
#define MAXM 20+10
#define INFINITO 99999999
#define UP 1
#define UP_LEFT 2
int nCases;
int n, m;
int d[MAXN], p[MAXN];
int D, P;
int diff[MAXN], sum[MAXN];
int C[MAXN+1][MAXM+1]; /* C[i][j] == (D(T)-P(T)) tal que |D(T)-P(T)| == minimal p/
S={1,..,i} e |T|=j */
int M[MAXN+1][MAXM+1]; /* M[i][j] == D(T)+P(T) == maximo p/ S={1,...i} |T|=j */
int E[MAXN+1][MAXM+1]; /* indica qual foi a escolha feita na posicao i, j (UP, ou
UP_LEFT)*/
int itens[MAXM];
int nItens;
/* Determina quais os itens que foram escolhidos */
void getItens(int i, int j){
if(i==0 || j==0) { return; }
if(E[i][j] == UP)
getItens(i-1, j);
else{ /*E[i][j] == UP_LEFT*/
getItens(i-1, j-1);
itens[nItens++] = i-1;
}
}
void knapsack(){
int i, j;
for (i=0; i<n; i++){
diff[i] = d[i] - p[i];
sum[i] = d[i] + p[i];
}
/* Caso Base */
for (j=0; j<=m; j++)
C[0][j] = INFINITO;
for (i=0; i<=n ;i++)
C[i][0] = 0;
for (j=0; j<=m; j++)
M[0][j]=0;
for (i=0; i<=n; i++)
M[i][0]=0;
for (i=1; i<=n; i++) {
for (j=1; j<=m; j++) {
if(MOD(C[i-1][j]) == MOD(C[i-1][j-1]+diff[i-1]) ){
/* Faz a escolha mais vantajosa */
if(M[i-1][j] > M[i-1][j-1]+sum[i-1]){
C[i][j] = C[i-1][j];
M[i][j] = M[i-1][j];
E[i][j] = UP;
}else{
C[i][j] = C[i-1][j-1] + diff[i-1];
M[i][j] = M[i-1][j-1] + sum[i-1];
E[i][j] = UP_LEFT;
}
}else{
if ( MOD(C[i-1][j]) < MOD(C[i-1][j-1]+diff[i-1]) ){
C[i][j] = C[i-1][j];
M[i][j] = M[i-1][j];
E[i][j] = UP;
}else{
C[i][j] = C[i-1][j-1] + diff[i-1];
M[i][j] = M[i-1][j-1] + sum[i-1];
E[i][j] = UP_LEFT;
}
}
}
}
getItens(n, m);
}
int main(){
int i;
nCases=1;
while(1){
scanf("%d %d", &n, &m);
if(n==0 && m==0)
break;
else
if(nCases>1)
printf("\n");
for (i=0; i<n; i++)
scanf("%d %d", &p[i], &d[i]);
printf("Jury #%d\n", nCases++);
nItens=0;
knapsack();
D=0; P=0;
for (i=0; i<m; i++){
D += d[itens[i]];
P += p[itens[i]];
}
printf("Best jury has value %d for prosecution and value %d for defence:\n", P, D);
for (i=0; i<m; i++)
printf(" %d", itens[i]+1);
printf("\n");
}
return 0;
}
Code: Select all
#include <bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[])
{
srand(time(NULL));
for (int cases = 1; cases <= 100; cases++)
{
int n = rand() % 100 + 1;
int m = min(rand() % n + 1, 20);
cout << n << ' ' << m << '\n';
for (int i = 1; i <= n; i++)
{
cout << rand() % 21;
cout << ' ';
cout << rand() % 21;
cout << '\n';
}
cout << '\n';
}
cout << "0 0\n";
return 0;
}