一只老风铃 于 2019-12-03 11:50:50 发布
本文探讨了01背包问题的动态规划解决方案，介绍了如何通过转移方程`dp[i][j]=max{ dp[i-1][j],dp[i-1][j-w[i]]+value[i] }`来确定物品的选择以最大化价值。进一步，文章提出了一种空间优化技巧，通过仅使用`dp[weight]`数组来迭代计算，利用后续迭代覆盖前一次的状态，从而减少空间开销。" 110675619,8241703,C++ STL迭代器详解：vector、list、map与unordered_map,"['C++', 'STL', '数据结构', '容器'] 先考虑传统01背包问题：给定N个物品的权重和价值，如何选择部分物品放入最大容量W的背包中，以获得最大总值？
其转移方程是： dp[i][j]表示前i件物品选择一些装入j容量包能获取的最大价值
那么 dp[i][j]=max{ dp[i-1][j],dp[i-1][j-w[i]]+value[i] }
也就是考虑第i件物品放入或者不放入背包，这两者中取最大值
如何填充这个dp数组？ 依次从第1件物品往n迭代，每一次迭代填充不同的背包容量。所求: dp[n][weight]
考虑由于每一次迭代都是仅仅用到前一次i-1的情况，可用后来值覆盖上述情况，节省空间
即 dp[weight]即可完成迭代计算
【问题】
You are given coins of different denominations and a total amount of money amount. Write
a function to compute the total number of ways to make up that amount using some of
those coins. Note: You may assume that you have an infinite number of each kind of coin
