ååã®ç¶ãã§ããååèšäºã®æåŸã§æããããåãã«å¯Ÿããåçç·šãšãªããŸããChatGPTãå©ããŠãããšããäžçãããã«æ¹åã§ããããšå€æããç¶ç·šãæžãã«è³ããŸããã
䞻匵: Unbounded Knapsack
çš®é¡ã®åç©ãããããç¡æ°ã«ãããããããã®åç©ã¯äŸ¡å€
ãšéã¿
ãæã£ãŠããã
ãããã®åç©ã¯å¹ç
ã®å€§ããæ¹ãã
ãšçªå·ä»ããããŠãããšããããŸãã
ã¯distinct ã§ãããã®ãšãããïŒããã§ãªãå Žåãéã¿ãåãã§äŸ¡å€ãå°ããåç©ã¯äžäœäºæãªã®ã§å
šãŠæšãŠãŠè¯ããïŒ
éã¿ã®æå€§å€ã ãšããããã®ãšãã容é
ã®æé©è§£ã®äžã§ãäžäœ
çš®é¡ã®ããããã䜿çšãããããªè§£ãå¿
ãååšããã
ããªãã¡ã [tex: j \ge U2/k] ãªãã°æé©è§£ã®ãã¡ äžäœ
çš®é¡ã®ããããã䜿çšãããããªãã®ãååšããïŒ
ãã®äž»åŒµã¯ïŒ[1,Lemma 5.1] ã®boundãããã«å³ãããããã®ã«ãªã£ãŠããŸãïŒå ã®è«æ[1]ã§ã¯
(see [12] for improvements on the constant factor)
ãšããŠããŸãããïŒãã®å®æ°åãæ¬è³ªãšèŠãŠããããã§ãïŒ
蚌æã«ç§»ãåã«ãããããŠã¹ã®ç¡¬è²šåé¡ã«ã€ããŠã®è£é¡ããã1ã€ç޹ä»ããŠãããŸãïŒ
è£é¡
éå ã§ãã£ãŠïŒ
ã§ãããã®ãèããïŒããã€ã³ããã¯ã¹
ãåºå®ããæïŒä»»æã®æŽæ°
ã¯
以å€ã®
ã®èŠçŽ ãå°ãªããšã1ã€äœ¿ã£ãããã§
ã®èŠçŽ ã®éè² æŽæ°çµåã§è¡šããïŒ
蚌æ
æ£æŽæ°ã®éå ã«å¯ŸãïŒ
ã
ã®éè² æŽæ°çµåã§è¡šããªãæå€§ã®æŽæ°ãšããïŒ
ããã§ïŒ
ã«å¯ŸãïŒ
ã§ããããšãç¥ãããŠããïŒ[2][3][4] ã«å¯ŸããŠã¯ïŒ
ãæãç«ã€ïŒ
ãšãããšïŒ
ã§ããïŒ
ãšãªãïŒãã ãªãäžã®äžçåŒãã
ã
ã®éè² æŽæ°çµåã§è¡šãïŒããã«
ã§ã¯ãªãèŠçŽ ãšããŠ
ãå ããããšã§æ¡ä»¶ã瀺ãããïŒ (蚌æäº)
ãããèžãŸããŠæ¬é¡ã«ç§»ããŸãïŒ
蚌æ
ããéã ã®æé©è§£ã§ãã£ãŠïŒTop
ã䜿çšããŠããªããã®ãåãããšããïŒãã®å€ééåã
ãšããïŒãã®äžã§å¹çãæå€§ã®åç©ã®çªå·ã
ãšããïŒ
ãšããïŒãŸãïŒ
ãšããïŒ
ããéãã®åèšã
ã®åæ°ã«ãªããããªéšåéåãéžã³ïŒåãé€ãããšãç¹°ãè¿ãïŒããã¯åç©ã
åä»¥äžæ®ã£ãŠããã°åžžã«å¯èœ.*1 ãããã£ãŠïŒæ®ãåç©ã¯é«ã
åã§ããïŒ
ãã®æäœã§åãé€ããåç©ã®ééã®åèšã
ãšããã°ïŒ
ãæç«ããïŒ*2
æŽæ° ã«è£é¡ãé©çšããïŒ
ã¯top
ã®åç©ãš
ã®éè² æŽæ°çµåã§ãã£ãŠïŒ
以å€ãå¿
ã䜿ããããªæ§æã§åããããšãã§ããïŒãŸãïŒå¹çãtop
ã®åç©ã䜿çšããŠããããšããïŒäŸ¡å€ãæžå°ããããšã¯ãªãïŒïŒèšŒæäºïŒ
çµè«
NDPC-Nã«ãããŠã¯ïŒä»¥äžã®DPãæ£åœã§ããããšã瀺ãããŸããïŒ
https://atcoder.jp/contests/ndpc/submissions/79070504
åäŸäœãã®ã€ããã§AIã«èããŠã¿ããè¯å®çã«è§£æ±ºã§ãããšã¯æããŸããã§ããïŒæãã¹ã......
[1] Timothy M. Chan, Qizheng He âMore on Change-Making and Related Problemsâ (2022), arXiv:2110.02503v1
[2] Jacques Dixmier "Proof of a conjecture by ErdÅs and Graham concerning the problem of Frobenius" (1990)
[3] Yahya Ould Hamidoune "On the Diophantine Frobenius Problem" (1998)
[4] Yahya Ould Hamidoune "Some results in additive number theory I: The critical pair theory" (2000)
*1:å䞊ã¹ãŠéãã®çޝç©åããšãã°é³©ã®å·£åçããéè€ãèŠã€ãã
*2:2çªç®ã®äžçå·ã¯ä»®å®ããïŒ3çªç®ã®äžçå·ã¯
ããåŸãïŒããã§ ã¯ååãšåæ§ã«
ãçžç°ãªã
以äžã®
ãã®åæ°ã
ååã£ãŠããããšãããããïŒæåŸã®äžçå·ã¯
ã
ã®å®çŸ©ããåŸãïŒ



