fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int NC = 23;
  6. array<uint16_t, 1<<NC> nd, us, bf;
  7.  
  8. int grd2(int c, const vector<int>& ia){
  9. 	int cnd = 99999999;
  10. 	{ //詰めている箱に入れられる最も大きな部品を詰める
  11. 		auto a = ia;
  12. 		int n=a.size();
  13. 		sort(a.rbegin(), a.rend());
  14. 		int cb = 0, sm = 0;
  15. 		while(a.size() >0){
  16. 			sm++; cb=0;
  17. 			for(int& z: a){
  18. 				if(z >=0 && cb + z <= c){
  19. 					cb += z; z = -9;
  20. 				}
  21. 			}
  22. 			a.erase(remove(a.begin(), a.end(), -9), a.end());
  23. 		}
  24. 		cnd = min(cnd, sm);
  25. 	}
  26. 	{ //残っている部品でCに近い組合せを作って採用
  27. 		vector<int>a = ia;
  28. 		int ans=0, n=a.size(), zan =n;
  29. 		sort(a.rbegin(), a.rend());
  30. 		while( zan >0){
  31. 			ans++;
  32. 			vector<int> um(c+2, -1);
  33. 			um[0] = 0;
  34. 			for(int i=0; i<n; i++) if(a[i]>0) for(int j=c-1; j>=0; j--){
  35. 				if(um[j] <0) continue;
  36. 				if(j + a[i] <= c && um[j+a[i]] <0) um[j+a[i]] = i;
  37. 			}
  38. 			int tg=-1;
  39. 			for(int j=c; j>=0; j--) if(um[j] >=0){ tg=j; break;}
  40. 			while(1){
  41. 				int z = um[tg];
  42. 				tg = tg - a[z];
  43. 				//cout << a[z] <<" ";
  44. 				a[z] = -9; zan--;
  45. 				if(tg==0) break;
  46. 			}
  47. 			//if(count(a.begin(), a.end(), -9)<n) cout << "/ ";
  48. 			//else {cout <<"\n"; break;}
  49.  
  50. 		}
  51. 		cnd = min(ans, cnd);
  52. 	}
  53.  
  54. 	{ //乱択5000回
  55. 		mt19937 mtr((unsigned)2018111515); //time(nullptr));
  56. 		vector<int>a = ia;
  57. 		int n=a.size();
  58. 		for(int g=0; g<5000; g++){
  59. 			shuffle(a.begin(), a.end(), mtr);
  60. 			int ck=c+30 ,sm=0;
  61. 			for(int i=0;i<n;i++){
  62. 				if(ck + a[i] > c){ sm++; ck = 0;}
  63. 				ck += a[i];
  64. 			}
  65. 			cnd = min(cnd, sm);
  66. 		}
  67. 	}
  68.  
  69. 	cout <<"乱択解: "<< cnd <<"\n";
  70. 	return cnd;
  71. }
  72.  
  73.  
  74. void fc(int c, const vector<int> v){
  75. 	const int n=v.size();
  76. 	for(int i=0; i< 1<<NC; i++) nd[i]=us[i]=bf[i]= 32000;
  77. 	nd[0] = 0; 
  78. 	for(int i=0; i< 1<<n; i++) for(int j=0; j<n ;j++) {
  79. 		if(i>>j &1) continue;
  80. 		int a = nd[i], b = us[i], nj = i | 1<<j;
  81. 		if(b + v[j] > c){ a++; b=0;}
  82. 		b += v[j];
  83.  
  84. 		if(nd[nj] > a || (nd[nj]==a && us[nj] > b)){
  85. 			nd[nj] = a; us[nj] = b;
  86. 			bf[nj] = j;
  87. 		} 
  88. 	}
  89.  
  90. 	cout<<"\nC = "<<c <<" :: a = {";
  91. 	for(int i=0;i<n;i++) cout<< v[i] <<" "; cout <<"}\n";
  92. 	int sm = accumulate(v.begin(), v.end(),0);
  93. 	cout << "必要数: " << nd[(1<<n) -1] <<" (N="<<n<< 
  94. 	        " 充填率 = " << 100.0*sm /(c * nd[(1<<n) -1]) <<"%)\n";
  95. 	deque<int> pt;
  96. 	for(int pf=(1<<n)-1; bf[pf] <32000;pf -= 1<<bf[pf]) pt.push_front(v[bf[pf]]);
  97. 	int ck=0;
  98. 	for(int i=0;i<n;i++){
  99. 		if(ck + pt[i] > c){ cout << "/ "; ck = 0;}
  100. 		cout << pt[i] <<" ";
  101. 		ck += pt[i];
  102. 	}
  103. 	cout <<"\n";
  104. 	//fpmt(c, v);
  105. 	int ri = grd2(c, v);
  106. 	if(ri != nd[(1<<n) -1]) cout <<"XXXXXXXXX wrong XXXXXXXXXX\n";
  107. }
  108.  
  109.  
  110.  
  111. int main(){
  112.  
  113. 	mt19937 mt((unsigned)20181115); //time(nullptr));
  114. 	vector<int> a;
  115. 	{ a = {8,5,10,6,4,5,8,5,9,6,9};  fc(30, a);}
  116. 	{ a = {33,61,58,41,50,21,60,64}; fc(120, a);}
  117. 	{ a = {33,61,58,41,50,21,60,64,23,45,67,78,89};fc(120, a);}
  118. 	{ a = {3,3,2,2,2,2,1,1,2,2,3,3,3,3,4,4,5,5,6};fc(7, a);}
  119. 	{ a = {3,3,2,2,2,2,3,3,2,2,2,2,3,3,3,2,2,2,2,2,2,};fc(7, a);}
  120. 	{ a = {6,5,3,2,2,2};fc(10, a);}
  121. 	{a = {770,316,349,194,222,556,491,347,147,977,404,196,383,854,707,207,487,960,936}; fc(1600,a);}
  122. 	cout <<"\n##### 以下ランダム出題と解 #####\n";
  123. 	for(int g=0; g<100; g++){
  124. 		const int su = mt()%7 + (g<10? 5:14) ;
  125. 		vector<int> z(su);
  126. 		for(int i=0; i<su; i++) z[i] = mt()%999 +1;
  127. 		int c = *max_element(z.begin(), z.end()) * (1.2 + mt()%1536/1024.0);
  128. 		c = (c+99)/100 * 100;
  129. 		fc(c,z);
  130. 	}
  131.  
  132. 	return 0;
  133. }
  134.  
Success #stdin #stdout 3.77s 64400KB
comments (?)
stdin 
Standard input is empty
stdout 
C = 30 :: a = {8 5 10 6 4 5 8 5 9 6 9 }
必要数: 3 (N=11 充填率 = 83.3333%)
5 10 6 4 5 / 8 8 5 9 / 6 9 
乱択解: 3

C = 120 :: a = {33 61 58 41 50 21 60 64 }
必要数: 4 (N=8 充填率 = 80.8333%)
61 58 / 33 21 64 / 50 60 / 41 
乱択解: 4

C = 120 :: a = {33 61 58 41 50 21 60 64 23 45 67 78 89 }
必要数: 6 (N=13 充填率 = 95.8333%)
33 64 23 / 61 58 / 41 78 / 50 67 / 21 89 / 60 45 
乱択解: 6

C = 7 :: a = {3 3 2 2 2 2 1 1 2 2 3 3 3 3 4 4 5 5 6 }
必要数: 8 (N=19 充填率 = 100%)
3 2 2 / 3 2 2 / 1 3 3 / 3 4 / 3 4 / 2 5 / 2 5 / 1 6 
乱択解: 8

C = 7 :: a = {3 3 2 2 2 2 3 3 2 2 2 2 3 3 3 2 2 2 2 2 2 }
必要数: 7 (N=21 充填率 = 100%)
3 2 2 / 3 2 2 / 3 2 2 / 3 2 2 / 3 2 2 / 3 2 2 / 3 2 2 
乱択解: 7

C = 10 :: a = {6 5 3 2 2 2 }
必要数: 2 (N=6 充填率 = 100%)
5 3 2 / 6 2 2 
乱択解: 2

C = 1600 :: a = {770 316 349 194 222 556 491 347 147 977 404 196 383 854 707 207 487 960 936 }
必要数: 6 (N=19 充填率 = 98.9896%)
194 222 977 207 / 316 347 936 / 404 707 487 / 491 147 960 / 349 383 854 / 770 556 196 
乱択解: 7
XXXXXXXXX wrong XXXXXXXXXX

##### 以下ランダム出題と解 #####

C = 1200 :: a = {720 865 934 737 322 284 249 515 866 745 }
必要数: 7 (N=10 充填率 = 74.25%)
322 866 / 934 249 / 865 284 / 745 / 737 / 720 / 515 
乱択解: 7

C = 1800 :: a = {519 775 285 357 439 803 317 471 329 232 }
必要数: 3 (N=10 充填率 = 83.8333%)
519 803 471 / 775 357 317 329 / 285 439 232 
乱択解: 3

C = 2100 :: a = {828 129 792 762 351 971 982 37 806 225 520 }
必要数: 4 (N=11 充填率 = 76.2262%)
828 129 792 351 / 762 806 520 / 971 982 37 / 225 
乱択解: 4

C = 1400 :: a = {548 909 291 720 282 803 612 }
必要数: 4 (N=7 充填率 = 74.375%)
548 803 / 720 612 / 909 291 / 282 
乱択解: 4

C = 1400 :: a = {902 517 52 755 403 277 606 715 290 953 89 }
必要数: 5 (N=11 充填率 = 79.4143%)
52 606 715 / 517 755 89 / 403 953 / 902 290 / 277 
乱択解: 5

C = 2400 :: a = {368 329 714 389 915 781 }
必要数: 2 (N=6 充填率 = 72.8333%)
368 329 915 781 / 714 389 
乱択解: 2

C = 2200 :: a = {727 878 767 430 983 73 567 }
必要数: 3 (N=7 充填率 = 67.0455%)
767 430 983 / 727 878 567 / 73 
乱択解: 3

C = 1700 :: a = {88 599 245 501 31 830 569 159 907 }
必要数: 3 (N=9 充填率 = 77.0392%)
599 31 159 907 / 88 245 501 830 / 569 
乱択解: 3

C = 1600 :: a = {321 134 249 835 134 275 726 983 186 717 173 }
必要数: 3 (N=11 充填率 = 98.6042%)
249 983 186 173 / 321 134 134 275 726 / 835 717 
乱択解: 3

C = 1000 :: a = {611 66 610 239 288 740 }
必要数: 3 (N=6 充填率 = 85.1333%)
239 740 / 611 66 288 / 610 
乱択解: 3

C = 1900 :: a = {615 750 370 294 655 143 713 441 91 396 278 819 537 259 }
必要数: 4 (N=14 充填率 = 83.6974%)
750 294 143 713 / 615 370 655 259 / 441 91 819 537 / 396 278 
乱択解: 4

C = 2400 :: a = {865 731 633 19 684 611 583 70 804 421 322 309 62 704 211 41 981 }
必要数: 4 (N=17 充填率 = 83.8646%)
865 731 804 / 633 684 70 309 704 / 611 421 322 62 981 / 19 583 211 41 
乱択解: 4

C = 2000 :: a = {243 946 641 854 815 401 71 746 92 665 1 330 726 17 890 578 126 221 932 796 }
必要数: 6 (N=20 充填率 = 84.0917%)
946 815 1 17 221 / 243 71 890 796 / 641 92 330 932 / 746 665 578 / 854 401 726 / 126 
乱択解: 6

C = 2200 :: a = {704 497 912 817 891 755 850 388 940 120 840 452 570 71 400 362 916 56 433 772 }
必要数: 6 (N=20 充填率 = 88.9848%)
388 840 916 56 / 497 940 400 362 / 891 755 120 433 / 704 850 570 71 / 912 817 452 / 772 
乱択解: 6

C = 1400 :: a = {642 344 727 205 644 219 638 29 335 429 455 360 431 909 603 780 170 }
必要数: 6 (N=17 充填率 = 94.2857%)
727 644 29 / 205 335 429 431 / 642 219 360 170 / 603 780 / 455 909 / 344 638 
乱択解: 6

C = 2300 :: a = {584 337 793 399 140 211 869 684 552 676 717 94 907 58 256 401 404 694 488 }
必要数: 5 (N=19 充填率 = 80.5565%)
337 399 907 256 401 / 793 140 211 58 404 694 / 584 552 676 488 / 869 684 717 / 94 
乱択解: 5

C = 2300 :: a = {928 138 761 782 943 807 852 381 313 969 464 825 264 91 46 788 333 165 121 344 }
必要数: 5 (N=20 充填率 = 89.6957%)
138 782 464 825 91 / 852 313 969 165 / 928 943 381 46 / 761 807 264 121 344 / 788 333 
乱択解: 5

C = 2200 :: a = {628 467 251 216 852 920 462 222 200 975 345 599 791 263 }
必要数: 4 (N=14 充填率 = 81.7159%)
628 251 975 345 / 467 216 462 791 263 / 852 920 222 200 / 599 
乱択解: 4

C = 2100 :: a = {704 268 790 804 792 278 762 956 37 68 610 398 167 551 877 }
必要数: 4 (N=15 充填率 = 95.9762%)
268 792 278 762 / 704 68 610 167 551 / 804 398 877 / 790 956 37 
乱択解: 4

C = 1300 :: a = {240 30 790 461 514 580 721 719 706 271 922 983 325 959 }
必要数: 7 (N=14 充填率 = 90.3407%)
580 719 / 30 271 983 / 325 959 / 790 461 / 514 721 / 240 922 / 706 
乱択解: 7

C = 1800 :: a = {42 550 692 717 537 709 4 671 174 647 774 392 322 955 }
必要数: 4 (N=14 充填率 = 99.8056%)
550 537 709 4 / 671 174 955 / 42 717 647 392 / 692 774 322 
乱択解: 4

C = 2200 :: a = {806 884 992 130 520 581 670 756 770 249 22 207 187 931 78 857 }
必要数: 4 (N=16 充填率 = 98.1818%)
884 130 770 22 207 187 / 520 670 931 78 / 581 756 857 / 806 992 249 
乱択解: 4

C = 1800 :: a = {338 594 816 47 207 181 768 4 228 645 66 402 873 731 276 623 }
必要数: 4 (N=16 充填率 = 94.4306%)
594 181 228 66 731 / 338 816 645 / 768 4 402 623 / 47 207 873 276 
乱択解: 4

C = 1500 :: a = {91 565 960 152 645 220 270 587 40 91 324 304 421 356 443 568 826 778 }
必要数: 6 (N=18 充填率 = 84.9%)
220 270 587 421 / 91 324 304 778 / 960 91 443 / 565 356 568 / 645 826 / 152 40 
乱択解: 6

C = 2200 :: a = {691 393 166 647 935 978 862 84 875 676 76 951 736 124 26 643 647 970 355 103 }
必要数: 5 (N=20 充填率 = 99.4364%)
691 647 862 / 84 676 124 26 643 647 / 875 970 355 / 166 978 951 103 / 393 935 76 736 
乱択解: 5

C = 1900 :: a = {697 759 788 509 418 828 613 404 720 985 846 102 812 767 }
必要数: 5 (N=14 充填率 = 97.3474%)
985 102 812 / 759 418 720 / 697 788 404 / 509 613 767 / 828 846 
乱択解: 6
XXXXXXXXX wrong XXXXXXXXXX

C = 2100 :: a = {386 939 984 869 374 716 295 337 976 435 782 345 150 899 309 }
必要数: 5 (N=15 充填率 = 83.7714%)
939 716 295 150 / 337 976 782 / 386 984 374 345 / 869 899 309 / 435 
乱択解: 5

C = 1200 :: a = {528 850 88 100 131 812 565 273 258 297 672 340 440 850 952 833 291 659 691 231 }
必要数: 9 (N=20 充填率 = 91.3056%)
528 672 / 88 812 297 / 131 833 231 / 850 340 / 273 258 659 / 850 291 / 440 691 / 100 952 / 565 
乱択解: 9

C = 2200 :: a = {607 74 395 56 658 258 822 378 222 277 98 504 892 814 143 626 249 966 303 755 }
必要数: 5 (N=20 充填率 = 82.7%)
74 56 258 822 98 892 / 395 222 814 143 626 / 607 378 249 966 / 658 277 504 755 / 303 
乱択解: 5

C = 1400 :: a = {763 228 830 979 902 362 45 685 503 518 353 906 861 608 302 93 294 452 929 170 }
必要数: 8 (N=20 充填率 = 96.2768%)
362 685 353 / 830 45 518 / 294 929 170 / 979 302 93 / 763 608 / 503 861 / 906 452 / 228 902 
乱択解: 8

C = 2600 :: a = {8 244 215 180 812 800 861 823 808 321 704 91 425 254 942 128 899 753 236 }
必要数: 4 (N=19 充填率 = 91.3846%)
180 812 800 808 / 244 861 425 942 128 / 8 704 899 753 236 / 215 823 321 91 254 
乱択解: 4

C = 2300 :: a = {823 718 908 804 126 170 536 72 536 389 930 417 244 45 88 638 462 }
必要数: 4 (N=17 充填率 = 85.9348%)
718 804 170 536 72 / 908 930 417 45 / 823 536 389 88 462 / 126 244 638 
乱択解: 4

C = 2600 :: a = {623 312 798 829 993 254 885 936 894 138 6 548 995 575 865 992 706 }
必要数: 5 (N=17 充填率 = 87.3%)
623 829 254 894 / 885 138 6 995 575 / 798 936 865 / 312 993 548 706 / 992 
乱択解: 5

C = 2100 :: a = {193 345 669 182 245 993 25 415 866 906 247 563 742 412 656 948 }
必要数: 5 (N=16 充填率 = 80.0667%)
245 906 948 / 669 866 563 / 345 182 415 742 412 / 193 993 247 656 / 25 
乱択解: 5

C = 2300 :: a = {88 637 535 67 396 715 648 152 791 951 789 998 454 740 833 }
必要数: 4 (N=15 充填率 = 95.587%)
152 951 454 740 / 715 791 789 / 67 396 998 833 / 88 637 535 648 
乱択解: 4

C = 1900 :: a = {996 325 563 757 363 984 508 868 209 566 188 631 753 661 545 }
必要数: 5 (N=15 充填率 = 93.8632%)
325 188 631 753 / 363 984 545 / 563 757 566 / 996 209 661 / 508 868 
乱択解: 5

C = 1900 :: a = {63 482 186 101 818 812 721 218 338 139 488 275 969 499 28 339 176 485 375 }
必要数: 4 (N=19 充填率 = 98.8421%)
482 186 818 139 275 / 101 812 488 499 / 218 338 969 375 / 63 721 28 339 176 485 
乱択解: 4

C = 2300 :: a = {122 126 197 677 353 441 853 365 191 404 139 194 572 193 912 295 473 985 }
必要数: 4 (N=18 充填率 = 81.4348%)
126 853 365 191 572 193 / 197 353 404 139 912 295 / 677 441 194 985 / 122 473 
乱択解: 4

C = 1700 :: a = {348 168 794 126 168 198 334 659 954 294 148 616 194 346 268 12 951 965 447 }
必要数: 5 (N=19 充填率 = 94%)
348 334 659 346 12 / 126 954 616 / 168 168 198 194 965 / 294 951 447 / 794 148 268 
乱択解: 5

C = 2300 :: a = {136 48 76 783 372 752 357 416 58 517 931 644 240 399 933 359 595 373 232 754 }
必要数: 4 (N=20 充填率 = 97.5543%)
136 48 76 752 357 931 / 783 416 58 644 399 / 240 933 373 754 / 372 517 359 595 232 
乱択解: 4

C = 1300 :: a = {832 704 411 607 184 154 452 328 144 920 13 912 922 533 299 89 }
必要数: 6 (N=16 充填率 = 96.2051%)
912 299 89 / 704 411 184 / 832 452 13 / 607 154 533 / 328 922 / 144 920 
乱択解: 6

C = 1200 :: a = {911 709 887 148 508 539 510 925 396 97 678 431 6 966 658 486 839 671 373 346 }
必要数: 10 (N=20 充填率 = 92.3667%)
396 431 373 / 539 658 / 709 486 / 510 678 6 / 839 346 / 508 671 / 148 925 97 / 966 / 911 / 887 
乱択解: 10

C = 2100 :: a = {993 22 639 893 510 57 798 76 761 657 833 940 528 980 372 366 626 928 }
必要数: 6 (N=18 充填率 = 87.1349%)
22 893 657 528 / 639 833 626 / 798 372 928 / 761 940 366 / 993 76 980 / 510 57 
乱択解: 6

C = 2600 :: a = {133 371 435 976 822 499 765 378 133 288 226 209 7 333 480 930 718 }
必要数: 3 (N=17 充填率 = 98.7564%)
133 435 822 499 378 333 / 765 133 288 209 7 480 718 / 371 976 226 930 
乱択解: 3

C = 1500 :: a = {967 450 793 470 932 379 940 431 429 331 355 349 681 778 }
必要数: 6 (N=14 充填率 = 92.0556%)
793 355 349 / 379 431 681 / 967 470 / 450 940 / 932 429 / 331 778 
乱択解: 6

C = 1700 :: a = {247 99 758 223 220 170 800 698 967 166 618 359 602 939 607 910 456 }
必要数: 6 (N=17 充填率 = 86.6569%)
223 220 800 456 / 170 618 910 / 758 939 / 99 967 607 / 698 359 602 / 247 166 
乱択解: 6

C = 2300 :: a = {898 332 521 29 480 858 223 832 146 963 213 787 372 897 482 755 603 710 368 }
必要数: 5 (N=19 充填率 = 91.0348%)
898 521 29 480 372 / 332 858 146 963 / 832 755 710 / 787 897 603 / 223 213 482 368 
乱択解: 5

C = 1700 :: a = {203 914 459 720 953 565 566 497 756 861 512 399 189 168 838 }
必要数: 6 (N=15 充填率 = 84.3137%)
861 838 / 459 720 512 / 953 566 168 / 203 914 565 / 497 756 399 / 189 
乱択解: 6

C = 2100 :: a = {625 725 997 901 844 500 906 507 855 311 250 810 625 201 794 865 801 }
必要数: 6 (N=17 充填率 = 91.4048%)
997 901 201 / 725 507 865 / 500 794 801 / 625 844 625 / 906 855 311 / 250 810 
乱択解: 6

C = 2500 :: a = {654 275 139 567 604 214 128 423 353 744 138 379 494 261 140 803 429 949 341 }
必要数: 4 (N=19 充填率 = 80.35%)
567 214 128 353 744 494 / 139 604 379 429 949 / 654 423 138 140 803 341 / 275 261 
乱択解: 4

C = 1400 :: a = {25 892 618 303 674 61 976 143 325 592 480 667 381 930 607 922 365 203 }
必要数: 7 (N=18 充填率 = 93.5102%)
892 303 203 / 325 592 480 / 25 61 381 930 / 618 143 607 / 674 667 / 976 365 / 922 
乱択解: 7

C = 1500 :: a = {312 177 398 823 593 737 126 329 837 427 265 855 450 524 682 264 }
必要数: 6 (N=16 充填率 = 86.6556%)
398 837 265 / 312 737 450 / 177 126 329 855 / 524 682 264 / 823 593 / 427 
乱択解: 6

C = 1400 :: a = {406 319 692 206 954 756 513 52 378 981 979 878 515 31 }
必要数: 6 (N=14 充填率 = 91.1905%)
878 515 / 378 981 31 / 406 979 / 319 954 52 / 756 513 / 692 206 
乱択解: 6

C = 1300 :: a = {711 543 508 998 571 818 907 705 494 357 395 709 579 242 283 38 176 }
必要数: 8 (N=17 充填率 = 86.8654%)
543 508 242 / 711 579 / 998 283 / 571 709 / 907 357 / 818 395 38 / 705 494 / 176 
乱択解: 8

C = 1600 :: a = {109 984 38 536 702 437 480 775 467 67 874 913 659 443 }
必要数: 5 (N=14 充填率 = 93.55%)
109 984 38 467 / 480 659 443 / 702 874 / 536 67 913 / 437 775 
乱択解: 5

C = 1500 :: a = {512 98 67 812 585 723 128 664 347 854 781 3 391 622 }
必要数: 5 (N=14 充填率 = 87.8267%)
98 812 585 3 / 512 128 854 / 67 781 622 / 723 347 391 / 664 
乱択解: 5

C = 1700 :: a = {290 831 799 639 647 632 177 302 143 493 55 742 508 507 788 28 860 }
必要数: 6 (N=17 充填率 = 82.7549%)
647 302 742 / 831 860 / 177 493 508 507 / 799 55 788 28 / 290 639 632 / 143 
乱択解: 6

C = 2100 :: a = {180 29 918 324 685 213 206 259 688 596 644 671 952 119 }
必要数: 4 (N=14 充填率 = 77.1905%)
180 324 644 952 / 29 685 596 671 119 / 918 213 259 688 / 206 
乱択解: 4

C = 2200 :: a = {735 563 424 53 4 197 410 116 357 449 896 338 213 783 813 }
必要数: 3 (N=15 充填率 = 96.2273%)
563 424 4 197 116 896 / 53 338 213 783 813 / 735 410 357 449 
乱択解: 3

C = 2700 :: a = {332 367 715 540 120 994 564 117 336 241 303 204 621 769 804 355 }
必要数: 3 (N=16 充填率 = 91.1358%)
332 120 564 336 241 303 804 / 715 540 117 204 769 355 / 367 994 621 
乱択解: 3

C = 1400 :: a = {197 582 720 827 893 572 942 503 896 42 802 789 368 541 992 280 852 494 184 566 }
必要数: 9 (N=20 充填率 = 95.5714%)
827 572 / 503 896 / 720 494 184 / 42 789 566 / 541 852 / 582 802 / 197 893 280 / 368 992 / 942 
乱択解: 9

C = 2600 :: a = {995 486 249 102 211 550 604 829 578 956 907 903 687 33 268 }
必要数: 4 (N=15 充填率 = 80.3654%)
211 604 829 956 / 102 907 903 687 / 995 486 249 550 33 268 / 578 
乱択解: 4

C = 2300 :: a = {218 294 222 67 670 189 932 21 731 102 550 698 767 598 }
必要数: 3 (N=14 充填率 = 87.8116%)
670 932 698 / 218 294 222 67 731 767 / 189 21 102 550 598 
乱択解: 3

C = 2100 :: a = {429 104 945 902 519 34 733 931 303 333 21 989 731 498 124 852 547 581 }
必要数: 5 (N=18 充填率 = 91.2%)
945 303 852 / 931 498 124 547 / 429 902 34 733 / 519 989 581 / 104 333 21 731 
乱択解: 5

C = 2000 :: a = {829 667 206 440 536 779 269 896 37 935 817 752 321 669 536 44 129 244 453 497 }
必要数: 6 (N=20 充填率 = 83.8%)
667 269 935 129 / 206 440 536 817 / 896 321 536 244 / 829 669 497 / 779 752 453 / 37 44 
乱択解: 6

C = 1200 :: a = {969 806 800 316 842 512 343 557 383 380 987 406 579 480 }
必要数: 8 (N=14 充填率 = 87.0833%)
806 383 / 842 343 / 800 380 / 557 579 / 512 480 / 987 / 969 / 316 406 
乱択解: 8

C = 1700 :: a = {539 379 706 333 89 190 959 994 864 993 76 312 962 485 916 105 434 619 188 }
必要数: 6 (N=19 充填率 = 99.4412%)
706 994 / 89 864 312 434 / 190 485 916 105 / 539 962 188 / 993 76 619 / 379 333 959 
乱択解: 7
XXXXXXXXX wrong XXXXXXXXXX

C = 1900 :: a = {936 990 174 436 209 407 697 174 436 171 306 129 180 130 167 786 194 131 548 839 }
必要数: 5 (N=20 充填率 = 84.6316%)
936 174 436 174 180 / 990 436 306 167 / 209 171 131 548 839 / 407 697 786 / 129 130 194 
乱択解: 5

C = 1500 :: a = {695 596 581 321 537 339 795 460 202 49 356 566 339 662 959 636 328 891 240 }
必要数: 7 (N=19 充填率 = 90.9714%)
339 202 959 / 460 49 662 328 / 321 537 636 / 695 795 / 596 891 / 581 566 339 / 356 240 
乱択解: 7

C = 2100 :: a = {632 680 122 289 626 321 86 815 264 329 220 579 764 411 89 469 560 }
必要数: 4 (N=17 充填率 = 86.381%)
289 321 815 264 411 / 86 220 764 469 560 / 680 122 626 579 89 / 632 329 
乱択解: 4

C = 2500 :: a = {654 783 627 505 680 468 842 498 898 705 171 641 935 990 757 825 354 349 167 }
必要数: 5 (N=19 充填率 = 94.792%)
641 935 757 167 / 654 505 842 498 / 783 468 898 349 / 680 990 825 / 627 705 171 354 
乱択解: 5

C = 2200 :: a = {551 53 526 403 729 84 709 726 989 112 299 975 64 949 527 536 984 762 987 237 }
必要数: 6 (N=20 充填率 = 84.8636%)
84 989 64 527 536 / 729 709 762 / 975 987 237 / 551 53 526 112 949 / 403 726 984 / 299 
乱択解: 6

C = 1200 :: a = {819 761 748 315 328 225 2 787 358 459 517 373 928 941 433 164 234 129 }
必要数: 8 (N=18 充填率 = 88.7604%)
761 2 433 / 819 373 / 748 315 129 / 941 234 / 225 928 / 787 358 / 459 517 164 / 328 
乱択解: 8

C = 1400 :: a = {683 412 194 415 295 141 775 260 42 84 908 519 937 828 }
必要数: 5 (N=14 充填率 = 92.7571%)
683 415 260 42 / 194 295 908 / 412 141 828 / 775 84 519 / 937 
乱択解: 5

C = 2500 :: a = {570 23 936 887 629 723 597 412 457 308 982 744 446 15 324 374 199 143 891 473 }
必要数: 5 (N=20 充填率 = 81.064%)
570 887 597 446 / 23 412 982 744 15 324 / 629 308 199 891 473 / 936 723 457 374 / 143 
乱択解: 5

C = 1600 :: a = {698 15 777 90 47 46 755 266 468 686 280 753 31 92 218 371 }
必要数: 4 (N=16 充填率 = 87.3906%)
777 90 47 686 / 755 753 92 / 698 46 266 218 371 / 15 468 280 31 
乱択解: 4

C = 2200 :: a = {408 139 16 202 742 259 279 491 981 670 233 943 972 867 694 549 435 739 }
必要数: 5 (N=18 充填率 = 87.4455%)
981 670 549 / 16 259 491 694 739 / 742 279 233 943 / 139 202 972 867 / 408 435 
乱択解: 5

C = 2500 :: a = {89 296 393 595 271 342 437 756 114 907 168 561 596 448 929 381 672 706 381 134 }
必要数: 4 (N=20 充填率 = 91.76%)
89 296 342 168 561 596 448 / 393 271 907 929 / 595 437 381 706 381 / 756 114 672 134 
乱択解: 4

C = 2500 :: a = {510 327 815 925 115 428 147 596 121 497 744 214 30 886 }
必要数: 3 (N=14 充填率 = 84.7333%)
925 147 596 121 497 214 / 327 115 428 744 886 / 510 815 30 
乱択解: 3

C = 2600 :: a = {549 503 670 981 804 277 959 268 33 634 457 816 465 660 624 628 804 161 110 322 }
必要数: 5 (N=20 充填率 = 82.5%)
981 959 660 / 549 503 804 634 110 / 277 268 465 624 804 161 / 670 457 816 628 / 33 322 
乱択解: 5

C = 2000 :: a = {478 75 488 23 721 136 450 160 985 361 799 938 102 387 }
必要数: 4 (N=14 充填率 = 76.2875%)
75 488 450 985 / 478 721 799 / 136 160 361 938 387 / 23 102 
乱択解: 4

C = 2200 :: a = {481 207 694 500 913 290 196 621 587 251 895 729 224 277 577 930 161 639 105 529 }
必要数: 5 (N=20 充填率 = 89.1455%)
694 500 729 277 / 913 196 930 161 / 207 621 251 895 224 / 290 587 577 639 105 / 481 529 
乱択解: 5

C = 1300 :: a = {795 62 245 463 92 365 410 510 160 338 966 871 677 708 608 }
必要数: 6 (N=15 充填率 = 93.2051%)
92 160 338 708 / 365 410 510 / 677 608 / 62 245 966 / 795 463 / 871 
乱択解: 6

C = 1400 :: a = {838 20 791 651 273 638 375 612 92 262 488 379 242 39 138 }
必要数: 5 (N=15 充填率 = 83.4%)
638 379 242 138 / 651 612 92 39 / 838 20 273 262 / 791 488 / 375 
乱択解: 5

C = 1900 :: a = {752 346 107 668 26 464 805 818 743 417 290 181 385 738 884 700 894 830 }
必要数: 6 (N=18 充填率 = 88.1404%)
743 417 738 / 346 668 884 / 752 26 290 830 / 818 181 894 / 805 385 700 / 107 464 
乱択解: 6

C = 2500 :: a = {464 896 896 144 311 355 307 808 330 551 880 752 941 644 379 505 773 346 558 }
必要数: 5 (N=19 充填率 = 86.72%)
896 355 307 941 / 464 896 808 330 / 144 644 379 773 558 / 311 551 880 752 / 505 346 
乱択解: 5

C = 1800 :: a = {202 717 563 86 604 211 225 319 986 515 554 644 181 802 963 77 47 }
必要数: 5 (N=17 充填率 = 85.5111%)
717 211 644 181 47 / 563 604 554 77 / 319 515 963 / 986 802 / 202 86 225 
乱択解: 5

C = 2200 :: a = {255 971 944 670 445 187 686 803 403 873 552 919 442 574 498 486 862 }
必要数: 5 (N=17 充填率 = 96.0909%)
686 442 574 498 / 971 187 552 486 / 403 873 919 / 944 445 803 / 255 670 862 
乱択解: 5

C = 1900 :: a = {134 658 176 670 280 460 181 947 400 66 704 110 152 733 }
必要数: 3 (N=14 充填率 = 99.4912%)
670 460 66 704 / 658 176 181 152 733 / 134 280 947 400 110 
乱択解: 3

C = 1400 :: a = {289 529 970 144 214 836 973 53 845 373 957 591 250 363 78 }
必要数: 6 (N=15 充填率 = 88.869%)
973 53 373 / 957 363 78 / 289 845 250 / 529 836 / 970 144 214 / 591 
乱択解: 6

C = 2600 :: a = {190 83 733 723 778 884 938 215 371 322 315 332 293 857 909 859 287 600 145 727 }
必要数: 5 (N=20 充填率 = 81.2385%)
778 884 938 / 733 371 322 315 859 / 215 332 857 909 287 / 83 723 293 600 145 727 / 190 
乱択解: 5

C = 1500 :: a = {85 574 356 771 113 97 15 566 558 838 142 102 751 578 498 706 225 99 }
必要数: 5 (N=18 充填率 = 94.32%)
85 97 566 751 / 356 113 706 225 99 / 558 838 102 / 771 142 578 / 574 15 498 
乱択解: 5

C = 2700 :: a = {478 925 966 995 627 973 170 95 93 686 542 714 662 595 254 }
必要数: 4 (N=15 充填率 = 81.25%)
925 966 95 714 / 478 995 973 254 / 627 170 93 542 662 595 / 686 
乱択解: 4

C = 2600 :: a = {213 283 59 504 880 764 444 995 638 432 280 988 193 769 }
必要数: 3 (N=14 充填率 = 95.4103%)
213 283 504 638 193 769 / 880 444 995 280 / 59 764 432 988 
乱択解: 3

C = 2500 :: a = {632 259 72 735 131 513 164 929 386 324 341 578 534 692 159 155 50 }
必要数: 3 (N=17 充填率 = 88.72%)
259 131 164 929 324 534 159 / 632 513 386 341 578 50 / 72 735 692 155 
乱択解: 3

C = 1600 :: a = {29 308 280 168 773 54 312 385 788 712 365 666 134 490 947 65 }
必要数: 5 (N=16 充填率 = 80.95%)
168 54 712 666 / 308 773 385 134 / 280 365 947 / 312 788 490 / 29 65 
乱択解: 5

C = 1500 :: a = {16 439 747 791 628 286 589 158 901 815 99 522 998 46 608 873 436 430 121 }
必要数: 7 (N=19 充填率 = 90.5048%)
791 158 430 121 / 99 522 873 / 589 901 / 628 815 46 / 16 439 747 286 / 998 436 / 608 
乱択解: 7

C = 2500 :: a = {839 255 383 26 126 551 159 292 276 950 9 242 296 161 106 }
必要数: 2 (N=15 充填率 = 93.42%)
839 383 551 159 292 276 / 255 26 126 950 9 242 296 161 106 
乱択解: 2

C = 2400 :: a = {695 665 905 871 577 106 127 274 265 883 672 647 753 374 527 646 }
必要数: 4 (N=16 充填率 = 93.6146%)
871 883 646 / 695 905 127 672 / 577 274 647 374 527 / 665 106 265 753 
乱択解: 4

C = 2600 :: a = {128 455 518 304 81 12 613 966 226 178 738 759 687 112 16 194 848 587 745 }
必要数: 4 (N=19 充填率 = 78.5288%)
455 304 687 112 194 848 / 518 12 738 587 745 / 81 613 966 178 759 / 128 226 16 
乱択解: 4
https://ideone.com/gsuOUp
ビンパッキング問題
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!