11003 - Boxes

yatsen · Post by **yatsen** » Wed Sep 27, 2006 10:30 am

Can anyone tell me what is wrong? I always WA.

/* Q11003 Boxes: by yatsen */
#include <stdio.h>
#include <string.h>
#define MaxN 1001
#define MaxLoad 3001
struct
{
	int weight;
	int load;
}box[MaxN];

int best[MaxN][MaxLoad];

int smaller(int x,int y)
{
	return (x<y?x:y);
}

int bigger(int x,int y)
{
	return (x>y?x:y);
}

void main()
{
	int i,j,k,n,ans,maxload;
	/*freopen("in11003.txt","r",stdin);*/
	while(scanf("%d",&n)==1)
	{
		if(n==0) break;
		for(i=1,maxload=0; i<=n; i++)
		{
			scanf("%d %d",&box[i].weight,&box[i].load);
			if(box[i].load>maxload) maxload=box[i].load;
		}
		memset(best,0,sizeof(best));
		for(i=1; i<=n; i++) best[i][box[i].load]=1;

		for(i=2; i<=n;  i++)  /* i: # of boxes stacked up so far */
		{
			for(j=maxload; j>=0; j--)            /* j: max load */
			{
				if(best[i-1][j] > 0)
				{
					if(j-box[i].weight>=0)
					{
						k=smaller(j-box[i].weight,box[i].load);
						best[i][k]=bigger(best[i][k],best[i-1][j]+1);
					}
					else
						best[i][j]=bigger(best[i][j],best[i-1][j]);
				}
			}
		}
		for(j=1,ans=best[n][0]; j<=maxload; j++)
			if(best[n][j]>ans) ans=best[n][j];
		printf("%d\n",ans);
	}
}

Tommy Wu · Post by **Tommy Wu** » Tue Jan 30, 2007 11:35 am

Code: Select all

#include <stdio.h>

struct DATA {
    int weight;
    int carry;
}box[1000];

int lis[1000][2];//[][0]:amount [][1]: carry

int main() {
    int i,j,N,tmp,max;
    while (scanf("%d",&N) && N) {
        for (i=max=0; i<N; i++)
            scanf("%d %d",&box[i].weight,&box[i].carry);
        lis[0][1]=box[0].carry;
        for (i=0; i<N; i++) {
            lis[i][0]=1,lis[i][1]=box[i].carry;
            for (j=0; j<i; j++) 
                if (box[i].weight<=lis[j][1]) 
                    if (lis[j][1]>lis[i][1] || lis[i][0]<lis[j][0]+1) {
                        lis[i][0]=lis[j][0]+1;
                        lis[i][1]=(lis[j][1]-box[i].weight)<?box[i].carry;
                    }
            max>?=lis[i][0];
        }
        printf("%d\n",max);
    }
    return 0;
}

This is my code...
The way I use to solve this problem is LIS/LDS, and it can output correct
result to every test data which had post above...(But it still get WA)

Can everyone tell me where's wrong in my code, please???

Sorry for my poor English grammar...

luckylove · Post by **luckylove** » Mon Mar 19, 2007 12:27 pm

I have a wrong answer
But i test a lot of case and it's correct
can everyone tell me where is my problem
or give me some special case:D
I use the alo Timos teach in first page
my code is over there
http://rafb.net/p/TdBhxG67.html
or
code:
#include<stdio.h>
int map[1000][3001];
void main()
{
　#ifndef ONLINE_JUDGE
　　freopen("11003.txt", "r", stdin);
　#endif
　int box[1000][2];
　int n,temp,max;
　int i,j;
　while(scanf("%d",&n))
　{
　　if(n==0)
　　　break;
　　for(i=0;i<n;i++)
　　　scanf("%d %d",&box[0],&box[1]);
　　for(i=0;i<n;i++)
　　　for(j=0;j<3001;j++)
　　　　map[j]=0;
　　　temp=0;
　　for(i=0;i<n;i++)
　　{
　　　map[box[1]]=1;
　　}
　　for(i=1;i<n;i++)
　　{
　　　for(j=0;j<3001;j++)
　　　{
　　　　if(map[i-1][j]>0)
　　　　{
　　　　　if(j-box[0]>=0)
　　　　　{
　　　　　　if(box[1]>j-box[0])
　　　　　　　temp=j-box[0];
　　　　　　else
　　　　　　　temp=box[1];
　　　　　　if(map[i][temp]>map[i-1][j])
　　　　　　{
　　　　　　　map[i][temp]=map[i][temp];
　　　　　　}
　　　　　　else
　　　　　　{
　　　　　　　map[i][temp]=map[i-1][j]+1;
　　　　　　}
　　　　　}
　　　　　else
　　　　　{
　　　　　　if(map[i-1][j]>map[i][j])
　　　　　　　map[i][j]=map[i-1][j];
　　　　　　else
　　　　　　　map[i][j]=map[i][j];
　　　　　}
　　　　}
　　　}
　　}
　　max=0;
　　i=n-1;
　　for(j=0;j<3001;j++)
　　{
　　　if(map[i][j]>max)
　　　{
　　　　max=map[i][j];
　　　}
　　}
　　printf("%d\n",max);
}

Thanks a lot

viniciusweb · Post by **viniciusweb** » Sat Jun 02, 2007 8:52 pm

Can someone post the correct output for the case below? Thanks.

Code: Select all

Jan · Post by **Jan** » Sat Jun 02, 2007 9:19 pm

My accepted code returns 24.

andysoft · Post by **andysoft** » Wed Apr 30, 2008 9:50 pm

Can anyone tell me why this problem cannot be solved correctly with Maximum Increasing Sequence algorithm?..
I have two arrays for DP: one is for length of longest sequence of boxes finishing at given box, and the second is to note how much "free weight" it still remains on given box... and just do the thing in O(n^2)..

mf · Post by mf » Thu May 01, 2008 12:13 am

Are you maximizing the length during your DP? If so, then it's not correct because sometimes it's better to have less boxes, but with more weight remaining for future boxes.

A fix is to make DP 2-dimensional -- add length of the sequence as an additional parameter to your DP, and try to maximize remaining weight.
I.e. for each 0<=i,j<=N compute the smallest weight of a tower of boxes of length exactly j, consisting of boxes with numbers 1 to i. This can be done in O(n^2) time.

andysoft · Post by **andysoft** » Thu May 01, 2008 1:05 pm

???????, mf
I got accepted when solved with your logic..
I had 2-dimensional matrix

andmej · Post by **andmej** » Sun Jun 22, 2008 8:46 am

mf wrote:Are you maximizing the length during your DP? If so, then it's not correct because sometimes it's better to have less boxes, but with more weight remaining for future boxes.

A fix is to make DP 2-dimensional -- add length of the sequence as an additional parameter to your DP, and try to maximize remaining weight.
I.e. for each 0<=i,j<=N compute the smallest weight of a tower of boxes of length exactly j, consisting of boxes with numbers 1 to i. This can be done in O(n^2) time.

Hello mf, can you give me an extra hint on how to compute the minimum length of a tower of length j supposing I know which i towers I can use?

Thanks. By the way, I'm reading a russian novel, Crime and punishment, by Fyodor Dostoevsky; and I like a lot russian names

mf · Post by mf » Mon Jun 23, 2008 5:07 pm

Let a[i, j] be the minimum weight of a tower, consisting of exactly j boxes, which are a subset of boxes with numbers i, i+1, ..., N. If no such tower exists, then a[i, j] = infinity. (or any other large number, for example, INT_MAX constant in C/C++)

Here's the recurrence for a[i, j]:

Code: Select all

if a[i+1, j-1] <= maximum_load_of_box[i]:
    a[i, j] = min(a[i+1, j-1] + weight_of_box[i], a[i+1, j])
else:
    a[i, j] = a[i+1, j]

And the base cases are: a[N+1, 0] = 0, and a[N+1, j] = infinity if j > 0.

tryit1 · Post by **tryit1** » Tue Sep 09, 2008 1:13 pm

hi ,
initially i thought this problem was the same as weights and measures (turtles).
I just sorted by serial number ,ie in the reverse order of input.

Now all 1 to i-1 boxes can be placed on top of box i.

so i construct the dp f(i,j) = min(f(i-1,j),f(i-1,j-1) + w(i)) where f(i,j) is the minimum weight of j boxes we select in the range 1 ... j

why does this work ?

If i sort the weights and measures by serial number it doesn't work . Is it because there u can place a on b or b on a but here u can only
have 1 ordering.

Btw can this problem be solved in o(nlogn) ?

m.shawkey · Post by **m.shawkey** » Tue Jul 16, 2013 5:04 pm

a test case
input

Code: Select all

output

Code: Select all

Neo_1234 · Post by **Neo_1234** » Sun Apr 13, 2014 8:08 am

can anyone please help me finding what's wrong in my code ? i am getting wa.
i used simple knapsack approach to find the maximum number of boxes.
it has passed all the inputs given here.
please help

Code: Select all

got ac.  :D 
a silly mistake.
can be solved easily by simple 0-1 knapsack.

brianfry713 · Post by **brianfry713** » Tue Apr 22, 2014 8:38 pm

Input:

Code: Select all

Correct output: 2

late_riser · Post by **late_riser** » Sat Sep 13, 2014 6:54 pm

Can anyone suggest me why getting WA? Below is my code.
My code gives output 9 in a test case above where Jan's code give output 24!

Code: Select all

#include<iostream>
#include<string.h>
#define WEIGHT 0
#define CAPA 1
using namespace std;

int arr[1005][2], dp[1003][6010];
int N;
int rec(int i, int balance_capa, int taken){

    if(i==N){

            return taken;
    }
    if(dp[i][balance_capa]!=-1) return dp[i][balance_capa];

    int res1=-1, res2=-1, res3 = -1;

        if(balance_capa-arr[i+1][WEIGHT]>=0)
                res1 = rec( i+1 , min(arr[i+1][CAPA],balance_capa-arr[i+1][WEIGHT]) , taken+1 );
        else res2 = rec(i+1,balance_capa,taken);

        res3 = rec(i+1,arr[i+1][CAPA],1);

    res2 = max(res3,res2);
    dp[i][balance_capa] = max(res1,res2);
    return dp[i][balance_capa];

}

int main(){

    while(cin>>N){

    if(N==0) break;
    for(int i=1;i<=N;i++) cin>>arr[i][WEIGHT]>>arr[i][CAPA];

    memset(dp,-1,sizeof(dp));
    cout<<rec(1,arr[1][CAPA],1)<<endl;
}

return 0;
}

OJ Board

11003 - Boxes

Output request

Re: 11003 - Boxes

Re: 11003 - Boxes

Re: 11003 - Boxes

Re: 11003 - Boxes

Re: 11003 - Boxes

Re: 11003 - Boxes

Re: 11003 - Boxes

Re: 11003 - Boxes

Re: 11003 - Boxes

Re: 11003 - Boxes