11003 - Boxes

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

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

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

Code: Select all

/* 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
New poster
Posts: 6
Joined: Tue Jan 23, 2007 12:32 pm
Location: Kaousiung,Taiwan
Contact:

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
New poster
Posts: 1
Joined: Sun Mar 18, 2007 5:32 pm

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
New poster
Posts: 24
Joined: Sun Nov 12, 2006 3:38 pm

Output request

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

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

Code: Select all

500
885 1945
1632 2766
857 1954
1845 2794
586 2542
986 2784
337 688
2322 2398
1073 1698
2549 625
2355 1602
2677 607
105 1593
1218 2005
2889 2376
272 1655
2245 425
970 1426
1972 2996
2522 181
418 1321
834 620
526 1702
2171 1261
351 122
261 1233
1732 2404
1108 46
2272 583
1366 2004
1986 485
988 1934
825 559
304 2393
531 2938
160 2329
814 1421
593 1843
1414 1202
1501 1961
2510 2528
2650 559
2169 2913
2037 1288
1963 2868
2495 372
2949 1618
2091 2336
2569 156
424 510
915 895
770 1694
2875 564
2205 2744
295 2442
531 1610
2688 1041
163 2391
2683 2738
2876 874
714 2983
2360 2559
2515 1563
2701 1414
89 642
593 857
1650 2843
1145 2011
573 1865
267 2546
2148 2340
2749 2670
731 2472
2149 1417
1504 1684
2705 2110
950 402
2796 1322
2565 1435
1465 1733
2519 1894
2526 898
2295 397
1565 1010
564 985
2926 1519
1852 2596
1508 2691
1766 1150
70 2495
489 153
215 1842
2034 685
748 77
2759 2803
1820 667
2904 167
2834 739
1094 337
858 2745
2778 920
1522 2817
1064 2972
209 1851
1746 2577
136 2547
2085 1280
211 2466
2164 1340
2802 58
1099 1749
536 1160
205 1633
1053 2217
1231 1804
750 1482
1095 1671
2966 86
283 2556
709 2579
1633 2758
2159 1678
1523 2934
1237 1936
634 991
1621 497
300 162
1287 1664
541 1821
1530 2384
1186 1388
109 1807
2460 103
483 2274
2903 97
1660 2104
1475 985
201 1755
1097 1692
694 2827
1379 2422
1281 1121
2721 1130
962 966
1825 1506
536 1230
1144 1061
2447 2474
1548 2708
1578 2405
280 725
1502 316
2612 2530
2606 1689
217 727
1719 125
1100 1099
2880 1882
2703 1847
272 2991
1393 2388
1827 446
504 2541
2089 669
837 295
708 2403
1542 2219
2159 1605
2017 576
2494 2272
1036 499
1400 2493
2404 2051
77 740
1504 1783
2174 655
2192 873
1185 850
391 1759
1494 1878
2919 461
1236 1768
616 1083
613 2968
687 1379
1064 1884
1234 86
1322 1881
1387 1941
1269 2201
2182 1156
62 2736
1008 1832
952 2873
1478 511
188 582
267 1313
2651 2951
334 132
971 182
1764 1635
1767 2080
648 2105
1270 2630
1433 903
2003 735
859 1196
1191 2901
769 2147
2270 1420
1824 253
2333 1169
2536 148
1391 2981
2702 2541
898 661
2196 2974
1155 2521
2803 2526
2490 87
139 2413
1873 2408
916 1492
1311 70
2911 1267
1161 2592
1364 2771
2240 223
207 694
1114 2796
91 998
2974 2328
1502 1080
1560 2225
1528 1863
2628 2110
1189 1424
784 1624
2959 1588
1061 1965
1952 2577
910 1642
2464 2186
1685 1350
986 2854
360 1266
1243 2435
738 572
2562 2914
1213 1597
2345 1930
404 2295
661 716
2811 916
499 255
1089 1900
689 1779
2266 1187
1778 2067
237 1927
144 2143
1990 2982
443 2315
1630 1703
1552 2391
1050 501
2997 248
2717 1892
2579 2169
152 325
1295 1915
891 2729
2059 665
956 1789
2171 1381
1410 1687
2292 2431
2797 607
2192 1548
2893 2340
1633 285
2932 2292
1618 1111
1740 672
1555 2166
2088 640
2536 225
1479 2563
1907 2128
1512 1957
999 451
2277 1693
1092 1365
905 1690
2034 2532
2554 1538
795 2087
1335 2662
2233 1410
1589 2571
579 889
2636 237
1405 105
2123 1387
1458 1134
1914 2476
2440 1824
2579 2525
2958 423
686 2576
1809 840
86 1436
1692 577
2754 1708
624 1258
168 1179
1195 1695
305 2328
2340 2808
2345 2509
2115 1166
2368 1238
774 473
27 466
540 1430
1397 2387
2165 1708
2681 1992
1466 147
1010 2715
681 1494
1354 2758
571 60
486 1137
580 637
2500 114
2554 2380
1561 393
2123 2930
1746 151
7 2190
2499 251
92 2006
534 1086
1872 1593
241 718
2249 1372
2287 1648
727 2246
572 2575
2313 2074
2164 246
929 289
2398 2149
1970 1642
353 2687
85 2476
194 2574
2932 2880
1814 2720
2738 436
1017 1375
2780 2693
2093 2951
2002 1704
163 486
1692 1248
1390 1128
142 1865
209 2706
752 1026
1730 1052
942 1518
516 2650
475 106
2842 2550
2456 422
639 911
688 1369
1295 2000
2013 2311
615 2873
490 2323
2869 719
846 2937
1670 2560
1984 368
412 2320
1058 1848
1033 2761
2393 2857
2347 2998
2955 847
751 2509
1288 1284
1498 1683
2984 2671
1832 2895
324 2380
1422 2859
1611 2753
2755 1922
838 1464
2231 871
2452 1331
2270 2135
113 1437
2133 2448
1002 463
1180 701
2174 813
1234 122
696 2402
1077 213
2220 303
1166 1798
1691 292
752 2577
529 2492
2382 1045
2219 2670
1967 2408
1071 2221
3000 2005
741 517
919 733
2895 2939
1472 1029
2409 1746
352 2248
2708 17
5 1976
2468 3
1366 2943
443 299
773 2693
2090 225
2555 2937
1486 2541
884 816
1424 1144
2361 1549
1903 666
723 1786
1429 1441
1854 2473
17 139
846 2624
360 237
607 2272
785 1086
2460 1136
2888 839
2106 368
1472 260
2879 2919
1912 2068
377 1455
689 482
1113 2231
702 486
967 2837
522 2134
2497 2411
86 1468
1069 2789
678 2985
1069 2868
2281 1485
2574 2320
2786 2726
2011 566
2157 2446
2913 945
2461 2965
569 131
2644 2060
604 444
2558 1100
2758 564
1541 1579
1054 452
2263 2850
465 2592
363 432
2481 1863
361 1207
1615 1124
1218 2556
89 1028
299 2037
809 1950
1551 2611
1952 206
271 2799
1937 882
1158 2310
777 1224
2018 394
1306 2741
0

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

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

My accepted code returns 24.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11003 - Boxes

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)..
Now I lay me down to sleep...
my profile

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 11003 - Boxes

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
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 11003 - Boxes

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

???????, mf
I got accepted when solved with your logic..
I had 2-dimensional matrix
Now I lay me down to sleep...
my profile

User avatar
andmej
Experienced poster
Posts: 158
Joined: Sun Feb 04, 2007 7:45 pm
Location: Medellin, Colombia

Re: 11003 - Boxes

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 :)
Runtime errors in Pascal are reported as Wrong Answers by the online judge. Be careful.

Are you dreaming right now?
http://www.dreamviews.com

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 11003 - Boxes

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.

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11003 - Boxes

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
New poster
Posts: 9
Joined: Tue Jun 11, 2013 2:58 pm

Re: 11003 - Boxes

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

a test case
input

Code: Select all

6
4 8
2 5
3 10
5 2
1 1
1 1
0
output

Code: Select all

5

Neo_1234
New poster
Posts: 3
Joined: Sat Jan 11, 2014 2:43 pm

Re: 11003 - Boxes

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 :cry:

Code: Select all

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11003 - Boxes

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

Input:

Code: Select all

9
2586 1687
2384 320
2841 2603
761 1192
1240 1793
1740 2194
2403 1168
2840 2052
2905 1516
0
Correct output: 2
Check input and AC output for thousands of problems on uDebug!

late_riser
New poster
Posts: 3
Joined: Wed Sep 18, 2013 2:05 pm

Re: 11003 - Boxes

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;
}


Post Reply

Return to “Volume 110 (11000-11099)”