hello-algo/ko/codes/pythontutor/chapter_dynamic_programming/knapsack.md at main

mirror of https://github.com/krahets/hello-algo.git synced 2026-11-02 03:05:24 +08:00

Files

T

Yudong Jin 2f561d3d51 feat(ko): add the Korean online edition (#2006 )

* feat(ko): add the complete Korean online edition

* Use UTF-8 for Python CI output on Windows

* Remove print-book promotion from the Korean site

* fix(ko): preserve emphasis before Korean particles

2026-10-29 03:46:43 +08:00

11 KiB

Raw Permalink Blame History

https://pythontutor.com/render.html#code=def%20knapsack_dfs%28wgt%3A%20list%5Bint%5D,%20val%3A%20list%5Bint%5D,%20i%3A%20int,%20c%3A%20int%29%20-%3E%20int%3A%0A%20%20%20%20%22%22%220-1%20%EB%B0%B0%EB%82%AD%3A%20%EC%99%84%EC%A0%84%20%ED%83%90%EC%83%89%22%22%22%0A%20%20%20%20%23%20%EB%AA%A8%EB%93%A0%20%EB%AC%BC%EA%B1%B4%EC%9D%98%20%EC%84%A0%ED%83%9D%EC%9D%84%20%EB%A7%88%EC%B3%A4%EA%B1%B0%EB%82%98%20%EB%B0%B0%EB%82%AD%EC%97%90%20%EB%82%A8%EC%9D%80%20%EC%9A%A9%EB%9F%89%EC%9D%B4%20%EC%97%86%EC%9C%BC%EB%A9%B4%20%EA%B0%80%EC%B9%98%200%EC%9D%84%20%EB%B0%98%ED%99%98%ED%95%9C%EB%8B%A4%0A%20%20%20%20if%20i%20%3D%3D%200%20or%20c%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%200%0A%20%20%20%20%23%20%EB%B0%B0%EB%82%AD%20%EC%9A%A9%EB%9F%89%EC%9D%84%20%EC%B4%88%EA%B3%BC%ED%95%98%EB%A9%B4%20%EB%B0%B0%EB%82%AD%EC%97%90%20%EB%84%A3%EC%A7%80%20%EC%95%8A%EB%8A%94%20%EC%84%A0%ED%83%9D%EB%A7%8C%20%EA%B0%80%EB%8A%A5%ED%95%98%EB%8B%A4%0A%20%20%20%20if%20wgt%5Bi%20-%201%5D%20%3E%20c%3A%0A%20%20%20%20%20%20%20%20return%20knapsack_dfs%28wgt,%20val,%20i%20-%201,%20c%29%0A%20%20%20%20%23%20%EB%AC%BC%EA%B1%B4%20i%EB%A5%BC%20%EB%84%A3%EC%A7%80%20%EC%95%8A%EB%8A%94%20%EA%B2%BD%EC%9A%B0%EC%99%80%20%EB%84%A3%EB%8A%94%20%EA%B2%BD%EC%9A%B0%EC%9D%98%20%EC%B5%9C%EB%8C%80%20%EA%B0%80%EC%B9%98%EB%A5%BC%20%EA%B3%84%EC%82%B0%ED%95%9C%EB%8B%A4%0A%20%20%20%20no%20%3D%20knapsack_dfs%28wgt,%20val,%20i%20-%201,%20c%29%0A%20%20%20%20yes%20%3D%20knapsack_dfs%28wgt,%20val,%20i%20-%201,%20c%20-%20wgt%5Bi%20-%201%5D%29%20%2B%20val%5Bi%20-%201%5D%0A%20%20%20%20%23%20%EB%91%90%20%EA%B2%BD%EC%9A%B0%20%EC%A4%91%20%EB%8D%94%20%ED%81%B0%20%EA%B0%80%EC%B9%98%EB%A5%BC%20%EB%B0%98%ED%99%98%ED%95%9C%EB%8B%A4%0A%20%20%20%20return%20max%28no,%20yes%29%0A%0A%0A%22%22%22%EC%8B%A4%ED%96%89%20%EC%BD%94%EB%93%9C%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20wgt%20%3D%20%5B10,%2020,%2030,%2040,%2050%5D%0A%20%20%20%20val%20%3D%20%5B50,%20120,%20150,%20210,%20240%5D%0A%20%20%20%20cap%20%3D%2050%0A%20%20%20%20n%20%3D%20len%28wgt%29%0A%0A%20%20%20%20%23%20%EC%99%84%EC%A0%84%20%ED%83%90%EC%83%89%0A%20%20%20%20res%20%3D%20knapsack_dfs%28wgt,%20val,%20n,%20cap%29%0A%20%20%20%20print%28f%22%EB%B0%B0%EB%82%AD%20%EC%9A%A9%EB%9F%89%EC%9D%84%20%EC%B4%88%EA%B3%BC%ED%95%98%EC%A7%80%20%EC%95%8A%EB%8A%94%20%EB%AC%BC%EA%B1%B4%EC%9D%98%20%EC%B5%9C%EB%8C%80%20%EA%B0%80%EC%B9%98%EB%8A%94%20%7Bres%7D%EC%9D%B4%EB%8B%A4%22%29&cumulative=false&curInstr=7&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

https://pythontutor.com/render.html#code=def%20knapsack_dfs_mem%28%0A%20%20%20%20wgt%3A%20list%5Bint%5D,%20val%3A%20list%5Bint%5D,%20mem%3A%20list%5Blist%5Bint%5D%5D,%20i%3A%20int,%20c%3A%20int%0A%29%20-%3E%20int%3A%0A%20%20%20%20%22%22%220-1%20%EB%B0%B0%EB%82%AD%3A%20%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98%EC%9D%84%20%EC%9D%B4%EC%9A%A9%ED%95%9C%20%ED%83%90%EC%83%89%22%22%22%0A%20%20%20%20%23%20%EB%AA%A8%EB%93%A0%20%EB%AC%BC%EA%B1%B4%EC%9D%98%20%EC%84%A0%ED%83%9D%EC%9D%84%20%EB%A7%88%EC%B3%A4%EA%B1%B0%EB%82%98%20%EB%B0%B0%EB%82%AD%EC%97%90%20%EB%82%A8%EC%9D%80%20%EC%9A%A9%EB%9F%89%EC%9D%B4%20%EC%97%86%EC%9C%BC%EB%A9%B4%20%EA%B0%80%EC%B9%98%200%EC%9D%84%20%EB%B0%98%ED%99%98%ED%95%9C%EB%8B%A4%0A%20%20%20%20if%20i%20%3D%3D%200%20or%20c%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%200%0A%20%20%20%20%23%20%EA%B8%B0%EB%A1%9D%EC%9D%B4%20%EC%9D%B4%EB%AF%B8%20%EC%9E%88%EC%9C%BC%EB%A9%B4%20%EB%B0%94%EB%A1%9C%20%EB%B0%98%ED%99%98%ED%95%9C%EB%8B%A4%0A%20%20%20%20if%20mem%5Bi%5D%5Bc%5D%20%21%3D%20-1%3A%0A%20%20%20%20%20%20%20%20return%20mem%5Bi%5D%5Bc%5D%0A%20%20%20%20%23%20%EB%B0%B0%EB%82%AD%20%EC%9A%A9%EB%9F%89%EC%9D%84%20%EC%B4%88%EA%B3%BC%ED%95%98%EB%A9%B4%20%EB%B0%B0%EB%82%AD%EC%97%90%20%EB%84%A3%EC%A7%80%20%EC%95%8A%EB%8A%94%20%EC%84%A0%ED%83%9D%EB%A7%8C%20%EA%B0%80%EB%8A%A5%ED%95%98%EB%8B%A4%0A%20%20%20%20if%20wgt%5Bi%20-%201%5D%20%3E%20c%3A%0A%20%20%20%20%20%20%20%20return%20knapsack_dfs_mem%28wgt,%20val,%20mem,%20i%20-%201,%20c%29%0A%20%20%20%20%23%20%EB%AC%BC%EA%B1%B4%20i%EB%A5%BC%20%EB%84%A3%EC%A7%80%20%EC%95%8A%EB%8A%94%20%EA%B2%BD%EC%9A%B0%EC%99%80%20%EB%84%A3%EB%8A%94%20%EA%B2%BD%EC%9A%B0%EC%9D%98%20%EC%B5%9C%EB%8C%80%20%EA%B0%80%EC%B9%98%EB%A5%BC%20%EA%B3%84%EC%82%B0%ED%95%9C%EB%8B%A4%0A%20%20%20%20no%20%3D%20knapsack_dfs_mem%28wgt,%20val,%20mem,%20i%20-%201,%20c%29%0A%20%20%20%20yes%20%3D%20knapsack_dfs_mem%28wgt,%20val,%20mem,%20i%20-%201,%20c%20-%20wgt%5Bi%20-%201%5D%29%20%2B%20val%5Bi%20-%201%5D%0A%20%20%20%20%23%20%EB%91%90%20%EA%B2%BD%EC%9A%B0%20%EC%A4%91%20%EB%8D%94%20%ED%81%B0%20%EA%B0%80%EC%B9%98%EB%A5%BC%20%EA%B8%B0%EB%A1%9D%ED%95%98%EA%B3%A0%20%EB%B0%98%ED%99%98%ED%95%9C%EB%8B%A4%0A%20%20%20%20mem%5Bi%5D%5Bc%5D%20%3D%20max%28no,%20yes%29%0A%20%20%20%20return%20mem%5Bi%5D%5Bc%5D%0A%0A%0A%22%22%22%EC%8B%A4%ED%96%89%20%EC%BD%94%EB%93%9C%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20wgt%20%3D%20%5B10,%2020,%2030,%2040,%2050%5D%0A%20%20%20%20val%20%3D%20%5B50,%20120,%20150,%20210,%20240%5D%0A%20%20%20%20cap%20%3D%2050%0A%20%20%20%20n%20%3D%20len%28wgt%29%0A%0A%20%20%20%20%23%20%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98%EC%9D%84%20%EC%9D%B4%EC%9A%A9%ED%95%9C%20%ED%83%90%EC%83%89%0A%20%20%20%20mem%20%3D%20%5B%5B-1%5D%20%2A%20%28cap%20%2B%201%29%20for%20_%20in%20range%28n%20%2B%201%29%5D%0A%20%20%20%20res%20%3D%20knapsack_dfs_mem%28wgt,%20val,%20mem,%20n,%20cap%29%0A%20%20%20%20print%28f%22%EB%B0%B0%EB%82%AD%20%EC%9A%A9%EB%9F%89%EC%9D%84%20%EC%B4%88%EA%B3%BC%ED%95%98%EC%A7%80%20%EC%95%8A%EB%8A%94%20%EB%AC%BC%EA%B1%B4%EC%9D%98%20%EC%B5%9C%EB%8C%80%20%EA%B0%80%EC%B9%98%EB%8A%94%20%7Bres%7D%EC%9D%B4%EB%8B%A4%22%29&cumulative=false&curInstr=20&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

11 KiB Raw Permalink Blame History

11 KiB

Raw Permalink Blame History