Community Answer

【General guidance】The answer provided below has been developed in a clear step by step manner.Step1/2Below are the solutions for all subparts from a to f:(a) Example: Let the denominations be d₁=1, d₂=3, d₃=4, and the weights be w₁=3, w₂=2, w₃=1, and the target value be V=6. Explanation:The optimal solution would be to use two coins of denomination 3, with a total weight of 4. However, using two coins of denomination 1 and two coins of denomination 2 would also sum up to 6 but have a total weight of 8.(b) Example: Let the denominations be d₁=1, d₂=2, and d₃=d₄=5, and the weights be w₁=1, w₂=2, w₃=5, w₄=10, and the target value be V=12. Explanation:The greedy algorithm would first use two coins of denomination 5, with a total weight of 10. Then, it would add two coins of denomination 1, with a total weight of 2, resulting in a total weight of 12. However, a better solution would be to use one coin of denomination 5 and one coin of denomination 2, with a total weight of 3.(c) A subproblem can be defined as finding the minimum weight of a set of coins that sum up to a value less than or equal to some target value k, using only the first i denominations of coins.(d) Let \( \mathrm{{M}{\left({i},{k}\right)}} \)be the minimum weight of a set of coins that sum up to a value less than or equal to k, using only the first \( \mathrm{{i}} \) denominations of coins. Then the recurrence rule is:\( \mathrm{{M}{\left({i},{k}\right)}=\min{\left\lbrace{M}{\left({i}-{1},{k}\right)},{w}_{{i}}+{M}{\left({i},{k}-{d}_{{i}}\right)}\right\rbrace}} \)Explanation:Please refer to solution in this step.Step2/2(e) Pseudocode for dynamic programming algorithm: ... See the full answer