题解 | #兑换零钱#

#include<iostream>
#include<vector>
using namespace std;
int main(void){
    /*
    看作完全背包问题，aim是背包的容量，n是物体的个数，-1是物体默认的收益，最大化装满以后背包的收益，-1的绝对值就是物体的个数，所以就是最小化物体的个数
    */
    int i, j, k, m, n, x, y = 0, z = 0, aim;
    cin>>n>>aim;
    vector<int> arr(n), dp(aim+1, -0xfffffff);
    for(i = 0; i < n; i++) scanf("%d", &arr[i]);
    dp[0] = 0;
    for(i = 0; i < n; i++) {
/*
j顺序递增的，此时的j-t[i].vi是逆序递增，但是j是顺序递增，又dp[0]=0，所以dp[j]的小值先算出来，小容量背包装了物品t[i].wi，不妨设容量是 jk.
随着j递增的，此时j-t[i].vi是逆序递增，当j-t[i].vi=jk时，或者j-t[i].vi是jk的整数倍时，就可以拿了小容量 t[i].wi放入到背包，相当是这件物品被放了两次，重复了，
j顺序递增可以用来求解 完全背包问题，也就是物品可以重复放多次，也就是物品数量无限。
下面的示例分别是j和j-t[i].vi，若j=2时装入了物品t[0]，那么j=4时，还可以继续装入物品t[0]
j     j-t[i].vi
2        0
3        1
4        2


然后来看正常的0-1背包问题的，j逆序递减的，此时的j-t[i].vi是顺序递减，所以dp[j]的右侧大值先算了出来，大容量背包装了物品，不妨设容量是 jb.
随着j递减的，此时的j-t[i].vi顺序递减的，又初始化的小容量都是0或者-inf，大容量装入小容量还是<0或者=0的，不会出现重复装的问题  
下面的示例分别是j和j-t[i].vi，若j=4时装入了物品t[2]，因dp[2]<=0，所以dp[4]基本不变的，而且后续不会重复装入
j     j-t[i].vi
5        3
4        2
3        1
2        0
*/
        for(j = arr[i]; j <= aim; j++) {
        // for(j = aim; j >= arr[i]; j--) {
            dp[j] = max(dp[j], dp[j - arr[i]] - 1);
        }
    }
    if(dp[aim] >= -aim) cout<<-dp[aim]<<endl; //收益-1，不可能>0，所以>=-aim包括0的情况
    else cout<<-1<<endl;
    return 0;
}

看作完全背包问题，aim是背包的容量，n是物体的个数，-1是物体默认的收益，最大化装满以后背包的收益，-1的绝对值就是物体的个数，所以就是最小化物体的个数

j顺序递增的，此时的j-t[i].vi是逆序递增，但是j是顺序递增，又dp[0]=0，所以dp[j]的小值先算出来，小容量背包装了物品t[i].wi，不妨设容量是 jk.

随着j递增的，此时j-t[i].vi是逆序递增，当j-t[i].vi=jk时，或者j-t[i].vi是jk的整数倍时，就可以拿了小容量 t[i].wi放入到背包，相当是这件物品被放了两次，重复了，

j顺序递增可以用来求解 完全背包问题，也就是物品可以重复放多次，也就是物品数量无限。

下面的示例分别是j和j-t[i].vi，若j=2时装入了物品t[0]，那么j=4时，还可以继续装入物品t[0]

j j-t[i].vi

2 0

3 1

4 2

然后来看正常的0-1背包问题的，j逆序递减的，此时的j-t[i].vi是顺序递减，所以dp[j]的右侧大值先算了出来，大容量背包装了物品，不妨设容量是 jb.

随着j递减的，此时的j-t[i].vi顺序递减的，又初始化的小容量都是0或者-inf，大容量装入小容量还是<0或者=0的，不会出现重复装的问题

下面的示例分别是j和j-t[i].vi，若j=4时装入了物品t[2]，因dp[2]<=0，所以dp[4]基本不变的，而且后续不会重复装入

j j-t[i].vi

5 3

4 2

3 1

2 0