关于背包问题：
- 01背包： 某类型物品最多只能取一次
- 完全背包：某类型的物品可以取n次
通常可以采取滚动数组进行优化，即每一轮研究新的物品到来对原问题解的影响。
【典型问题-置换硬币】
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
采取dp[k]表示置换出k面额最少的使用硬币数量。有：
如dp[k]=min(dp[k],dp[k-value]) // 每一轮研究value硬币引入是否会减少组配k总数量减少这里需要注意两个问题：
- 其一是dp[k-value]其是否可以组配 若不能组配，那么应该不能影响到dp[k] 解决方法是初始化一个INT_MAX表示无法组配
- 其二是dp[k]的迭代方向必须为 k=0=>aim 因为这样在计算dp[k]时，dp[k-value]是在本轮计算=》解决了使用多个value情况
完全背包问题由于数量没有限制，迭代计算方向为0=》sum 以确保一轮可以使用任意多个同类型硬币int main()
{int n,aim;cin>>n>>aim;vector<int> arr(n,0);for(int i=0;i<n;i++)cin>>arr[i];vector<int> dp(aim+1,INT_MAX);//dp[i]表示置换i最少硬币数量 -1表示无法置换出dp[0]=0;for(int i=0;i<n;i++) //每次考虑引进新的硬币能否减少 硬币数量{for(int j=arr[i];j<=aim;j++) //计算dp[j]{if(dp[j-arr[i]]!=INT_MAX)dp[j]=min(dp[j],dp[j-arr[i]]+1); //使用一块arr[i]硬币 }} if(dp[aim]!=INT_MAX)cout<<dp[aim]<<endl;elsecout<<-1<<endl;}
【典型问题-置换硬币】
给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币最多使用一张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。
由于一种硬币最多使用1张，那么迭代计算方向必须为aim=>0 这样当计算dp[k]时，
dp[k-value]一定是上一轮计算结果（本轮还没有计算到它）可以确保dp[k]最多考虑一个value硬币
int n,aim;cin>>n>>aim;vector<int> arr(n,0);for(int i=0;i<n;i++)cin>>arr[i];vector<int> dp(aim+1,INT_MAX);//dp[i]表示置换i最少硬币数量 -1表示无法置换出dp[0]=0;for(int i=0;i<n;i++) //每次考虑引进新的硬币能否减少 硬币数量{for(int j=aim;j>=arr[i];j--) //计算dp[j]{if(dp[j-arr[i]]!=INT_MAX)dp[j]=min(dp[j],dp[j-arr[i]]+1); //使用一块arr[i]硬币}} if(dp[aim]!=INT_MAX)cout<<dp[aim]<<endl;elsecout<<-1<<endl;