624 - CD
Moderator: Board moderators
Maintain another array to store the last element from which the current value is made. Suppose you used 'val' to get from k to p. So, p = k + val. So, sq[p] = val (sq is the sequence array). Or you can use sq[p] = k. Its upto your implementation.
Hope it helps.
Hope it helps.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Jan, thank you for the advice, but I couldnt understand it completely. I made an additional array (sq for us to better understand each other) and store there the length of the track. My Dynamic Programming part of code looks like this:
But this works only from time to time.. 50% of tests give ok sequence, 50% - only the same number several times.
Hope you'll help me, TIA.
Code: Select all
//a is Dynamic array, l (L) is array with lengths of tracks, sq - sequence
for i:=1 to n do //n - number of tracks
for j:=1 to m do //m - tape length
if l[i]>j then //knapsack algorithm
a[i,j] := a[i-1,j]; //...
else//...
begin//...
a[i,j] := max (a[i-1,j],l[i]+a[i-1,j-l[i]]); //end of knapsack algrorithm
if sq[j]=0 then //storing the sequence
sq[j] := l[i] //storing the sequence
end;
//Then sorting and outputting, I'll have no prob with that
Hope you'll help me, TIA.
Now I lay me down to sleep...
my profile
my profile
I have edited your code. Check it.
Now You can find the sequence easily. Check the pseudocode below.
P.S. I m not a pascal programmer. So, there can be errors
.
Hope these help.
Code: Select all
//a is Dynamic array, l (L) is array with lengths of tracks, sq - sequence
for i:=1 to n do //n - number of tracks
for j:=1 to m do //m - tape length
if l[i]>j then //knapsack algorithm
begin
a[i,j] := a[i-1,j]; //...
sq[j] := 0;
end;
else//...
begin//...
a[i,j] := a[i-1,j];
sq[j] := 0;
if a[i,j] < l[i]+a[i-1,j-l[i]] then
begin
a[i,j] :=l[i]+a[i-1,j-l[i]];
sq[j] := l[i]; //storing the sequence
end;
end;
Code: Select all
findsequence (i,j)
{
if(i<0)
return;
if(sq[j] == 0)
findsequence(i-1,j);
else
{
print(sq[j]);
findsequence(i-1,j-sq[j]);
}
}
![:lol:](./images/smilies/icon_lol.gif)
Hope these help.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Thank you for help. I have modified the code you send me a bit, and wrote function of finding the sequence, still I got WA... ![:(](./images/smilies/icon_frown.gif)
Maybe you may look what is wrong?..
The DP:
After the DP I execute the path-finding function, which stores the path in array ans. Here is this function: (I execute it with 0,a[n,m] params by the way)
After it usual sorting (bubble one) and output like in sample output.
![:(](./images/smilies/icon_frown.gif)
Maybe you may look what is wrong?..
The DP:
Code: Select all
for i:=1 to n do
for j:=1 to m do
if l[i]>j then
a[i,j] := a[i-1,j];
else
begin
a[i,j] := a[i-1,j];
if a[i,j] < l[i]+a[i-1,j-l[i]] then
begin
a[i,j] :=l[i]+a[i-1,j-l[i]];
sq[j] := l[i]; //storing the sequence
end;
end;
Code: Select all
procedure metalblack (i,j: integer); //i - total length of this sequence, j - like you offered
begin
if (sq[j]=0) then
metalblack (i,j-1)
else
begin
k := k + 1; //add new item to ANS array
ans[k] := find (sq[j]); //add new item to ANS array. Find - it finds the index of the track with given length in array L (which is inputted) by just looking all elements.
if i+sq[j]>=a[n,m] then exit; //if we took all needed elements to the output sequence, we gotta exit this function.
metalblack (i+sq[j],j-sq[j])//otherwise, continue, with adding current length to i, and subtracting it from j
end
end;
Now I lay me down to sleep...
my profile
my profile
You should initialize sq[], if you use your code. Or you can use the code I posted already.
Your metalblack looks correct to me. But you can think of findsequence (i,j) again. What if you call findsequence (n,m)?
Hope these help.
Your metalblack looks correct to me. But you can think of findsequence (i,j) again. What if you call findsequence (n,m)?
Hope these help.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Well, I did like you said now, but it didn't even pass default i/o tests.
Maybe let's talk about the prog in general, not about the functions separately? Maybe error is hidden outside functions.
Sorry, for Pascal'ing again, but I tried to make it as clear as I can.
Maybe let's talk about the prog in general, not about the functions separately? Maybe error is hidden outside functions.
Sorry, for Pascal'ing again, but I tried to make it as clear as I can.
Code: Select all
program Project2;
{$R-}{$S-}{$Q-}
type
integer = longint;
function max(a,b: integer): integer; //just 'maximum' function
begin
result := a;
if b>a then result:=b
end;
var
a: array [-1..20,-1..20000] of integer; //DP
sq: array [1..20000] of integer;
ans: array [1..40] of integer;//Answer for sorting and outputting
l: array [1..20] of integer; //Given lengths
i,j,m,n,k,t: integer;
function find(v: integer): integer; //finding element by its length
var
i: integer;
begin
for i:=1 to n do
if l[i] = v then
begin
result := i;
exit
end
end;
procedure findsequence (i,j: integer); //your findSequence just in PAS
begin
if(i<0) then
exit;
if(sq[j] = 0) then
findsequence(i-1,j)
else
begin
k := k + 1;
ans[k] := find(sq[j]);
findsequence(i-1,j-sq[j])
end;
end;
procedure doOut; //just outputting
var
i: integer;
begin
for i:=1 to k do
write (l[ans[i]],' '); //length of the track, index of which is stored in ans[i]
writeln ('sum:',a[n,m])
end;
procedure sort; //Bubblesort, because, you know, the task description says we got to output in the same sequence as inputted
var
i,j,temp: integer;
begin
for i:=1 to k-1 do
for j:=1 to k-i do
if ans[j]>ans[j+1] then
begin
temp := ans[j];
ans[j] := ans[j+1];
ans[j+1] := temp
end
end;
begin
while not eof do //while (cin>>m>>n)
begin
read (m);
read (n);
for i:=1 to 20 do
for j:=1 to 20000 do a[i,j] := 0; //initializing of DP array
for i:=1 to n do
begin
read (l[i]); //for(i=1;i<=n;i++) cin>>l[i];
ans[i] := 0 //init the ANS array
end;
for i:=1 to n do //init of DP array as in KnapSack algorithm
a[i,0] := 0;
for j:=1 to m do
a[0,j] := 0;
for i:=1 to 20000 do
sq[i] := 0; //init of SQ (won't spoil at least)
//DP as you offered
for i:=1 to n do
for j:=1 to m do
if l[i]>j then
begin
a[i,j] := a[i-1,j];
sq[j] := 0;
end
else
begin
a[i,j] := a[i-1,j];
sq[j] := 0;
if a[i,j] < l[i]+a[i-1,j-l[i]] then
begin
a[i,j] :=l[i]+a[i-1,j-l[i]];
sq[j] := l[i];
end;
end;
k := 0;//k is number of elements in ANS
findsequence (n,m); //find sequence with needed params
sort; //bubble sort
doOut; //output
end;
end.
Now I lay me down to sleep...
my profile
my profile
I have updated some parts. You have to use a 2d sq.
It gives WA, too. May be there is a problem with eof handling. It prints one extra line when eof is detected.
Code: Select all
program Project2;
{$R-}{$S-}{$Q-}
type
integer = longint;
var
a: array [-1..20,-1..20000] of integer; //DP
sq: array [-1..20,-1..20000] of integer;
ans: array [1..40] of integer;//Answer for sorting and outputting
l: array [1..20] of integer; //Given lengths
i,j,m,n,k,t: integer;
function find(v: integer): integer; //finding element by its length
var
i: integer;
begin
for i:=1 to n do
if l[i] = v then
begin
result := i;
exit
end
end;
procedure findsequence (i,j: integer); //your findSequence just in PAS
begin
if(i=0) then
exit;
if(sq[i,j] = 0) then
findsequence(i-1,j)
else
begin
k := k + 1;
ans[k] := sq[i,j];
//ans[k] := find(sq[i,j]);
findsequence(i-1,j-sq[i][j])
end;
end;
procedure doOut; //just outputting
var
i: integer;
begin
for i:=1 to k do
write (l[ans[i]],' '); //length of the track, index of which is stored in ans[i]
writeln ('sum:',a[n,m])
end;
procedure sort; //Bubblesort, because, you know, the task description says we got to output in the same sequence as inputted
var
i,j,temp: integer;
begin
for i:=1 to k-1 do
for j:=1 to k-i do
if ans[j]>ans[j+1] then
begin
temp := ans[j];
ans[j] := ans[j+1];
ans[j+1] := temp
end
end;
procedure doOut1; //just outputting
var
i: integer;
begin
for i:=1 to k do
write (ans[k-i+1],' '); //length of the track, index of which is stored in ans[i]
writeln ('sum:',a[n,m])
end;
begin
while not eof(input) do //while (cin>>m>>n)
begin
read (m);
read (n);
for i:=1 to 20 do
for j:=1 to 20000 do
begin
a[i,j] := 0; //initializing of DP array
sq[i,j] := 0;
end;
for i:=1 to n do
begin
read (l[i]); //for(i=1;i<=n;i++) cin>>l[i];
ans[i] := 0 //init the ANS array
end;
for i:=1 to n do //init of DP array as in KnapSack algorithm
a[i,0] := 0;
for j:=1 to m do
a[0,j] := 0;
//DP as you offered
for i:=1 to n do
for j:=1 to m do
if l[i]>j then
begin
a[i,j] := a[i-1,j];
sq[i,j] := 0;
end
else
begin
a[i,j] := a[i-1,j];
sq[i,j] := 0;
if a[i,j] < l[i]+a[i-1,j-l[i]] then
begin
a[i,j] :=l[i]+a[i-1,j-l[i]];
sq[i,j] := l[i];
end;
end;
k := 0;//k is number of elements in ANS
findsequence (n,m); //find sequence with needed params
//sort; //bubble sort
doOut1; //output
end;
end.
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Jan, man, thank you for your colossal help!!!!!
I will try to find the mistake in this code, because even with not printing the last "\n" it gives WA.
I will try to find the mistake in this code, because even with not printing the last "\n" it gives WA.
Now I lay me down to sleep...
my profile
my profile
You are welcome. When eof is detected the code prints 'sum:0'. I was talking about this. However, good luck!
Ami ekhono shopno dekhi...
HomePage
HomePage
Help!
Hello, this is my code.
I've read all the posts about 624, but I still can't find where my problem is.
I sent this code and got RE(signal 11) .
Would you please help me find where My code is wrong?
Thank you very much!
I've read all the posts about 624, but I still can't find where my problem is.
I sent this code and got RE(signal 11) .
Would you please help me find where My code is wrong?
Thank you very much!
Code: Select all
#include<stdio.h>
#define limit 20000
int main(void){
int N;
int MW;
int total;
int c[25][limit+1];
int item[25][limit+1];
int cd[25];
int i,j;
int temp;
int a[25];
while(scanf("%d",&MW)!=EOF){
scanf("%d",&N);
total=0;
a[0]=0;
for(i=1;i<=N;i++)
scanf("%d",&a[i]);
for(j=0;j<=MW;j++)c[0][j]=0;
for(i=1;i<=N;i++){
c[i][0]=0;
item[0][i]=0;
for(j=1;j<=MW;j++){
if(a[i]>j){
c[i][j]=c[i-1][j];
item[i][j]=item[i-1][j];
}
else{
if(c[i-1][j]>=c[i-1][j-a[i]]+a[i]){
c[i][j]=c[i-1][j];
item[i][j]=item[i-1][j];
}
else{
c[i][j]=c[i-1][j-a[i]]+a[i];
item[i][j]=i;
}
}
}
}total+=c[N][MW];
temp=0;
for(i=MW,j=0;i>=1;i-=a[item[N][i]],j++)
cd[j]=a[item[N][i]];
for(i=j-1;i>=0;i--){
printf("%d ",cd[i]);
temp+=cd[i];
if(temp==total)break;
}
printf("sum:%d\n",total);
}
return 0;
}
-
- New poster
- Posts: 21
- Joined: Thu Jun 14, 2007 11:45 pm
If there are more then one answer, can I print anyone of then?
Im getting WA, and I can't find the error.
Thank you.
Im getting WA, and I can't find the error.
Code: Select all
AC
Last edited by renato_ferreira on Tue Aug 14, 2007 9:08 pm, edited 1 time in total.
Try the cases.
Input:
Output:
And yes. Multiple outputs are supported. Hope these help.
Input:
Code: Select all
32 5 14 1 11 5 9
15 8 13 10 20 19 4 19 7 20
29 6 20 15 5 7 20 19
60 8 10 8 3 11 3 19 7 8
81 7 19 20 12 18 14 14 1
Code: Select all
1 5 11 14 sum:31
4 10 sum:14
5 7 15 sum:27
3 3 7 8 8 11 19 sum:59
1 12 14 14 19 20 sum:80
Ami ekhono shopno dekhi...
HomePage
HomePage
-
- New poster
- Posts: 21
- Joined: Thu Jun 14, 2007 11:45 pm
hello , I got WA in this problem, could anybody please help me to find out what cause WA, thanks very much ![:D](./images/smilies/icon_biggrin.gif)
![:D](./images/smilies/icon_biggrin.gif)
Code: Select all
got AC
Last edited by toni on Tue Sep 18, 2007 5:10 am, edited 1 time in total.
May be some sort of initialization problem. Check the cases...
Input:
Output:
Hope these help.
Input:
Code: Select all
52 5 15 1 10 5 19
29 10 5 6 6 2 8 2 12 16 3 8
47 9 5 3 14 13 3 2 17 19 16
58 9 12 19 10 13 8 20 16 15 4
62 5 14 14 5 2 12
94 16 8 5 3 18 18 20 4 2 10 19 17 16 11 3 9 7
51 5 5 9 7 6 11
80 13 11 7 2 14 9 10 4 5 15 17 1 7 17
82 16 5 20 7 4 18 19 19 3 10 2 14 16 20 19 5 11
Code: Select all
1 5 10 15 19 sum:50
2 2 3 6 8 8 sum:29
3 3 5 17 19 sum:47
4 8 10 16 20 sum:58
2 5 12 14 14 sum:47
2 3 3 4 5 7 8 9 16 17 20 sum:94
5 6 7 9 11 sum:38
1 2 4 5 7 7 9 11 17 17 sum:80
2 3 4 5 5 7 10 11 16 19 sum:82
Ami ekhono shopno dekhi...
HomePage
HomePage