动态规划（背包问题）

背包问题

01背包

每个物品最多取一次

for(int i = 1; i <= n;i ++ ){
    cin >> v >> w; //边输入边处理
    for(int j = m; j >= v; j -- ){ //容量必须大于可选体积
        f[j] = max(f[j],f[j - v] + w);
        //f[i][j] = max(f[i - 1][j], f[i - 1][j - v] + w) j 正序
        //f[j]不选，f[j-v]+w 选择 取两者最大
    }
    /*关于一维为什么j要逆序。
    因为正序f[j]的可能取到i(本轮)轮的f[j]而不是i-1轮的。
    如果j正序：
    在i轮，在j>=v的条件下v=4,w=5
    f[j](j取4,5,6,7,  8)
    =max(f[j],f[j-v]( j-v 取0,1,2,3, 4(而这个4，则会计算f[i][4],而不是f[i-1][4]) )+w);
    如果j逆序：
    在i轮，在j>=v的条件下v=4,w=5
    不会出现f[i][j-v]情况，因为f[j-v]一直是第一次出现。 
    */
}
   

完全背包

每个物品可无限取

$f[i,j]=max(f[i−1,j],f[i−1,j−v]+w,f[i−1,j−2v]+2w,f[i−1,j−3v]+3w,…..)$

$f[i,j−v]=max( f[i−1,j−v],f[i−1,j−2v]+w,f[i−1,j−3v]+2w,…..)$

通过上述替换，可以得到 f[i][j]=max(f[i−1][j],f[i][j−v]+w)

for(int i = 1; i <= n; i++){
    cin >> v >> w;
    for(int j = v;j <= m; j++){//这里j=v,是因为要保证j-v>=0
        f[j] = max(f[j], f[j - v] + w);
    }
}
/*上一篇代码中，解释过，逆序是为了保证更新当前状态时，用到的状态是上一轮的状态，保证每个物品只有一次或零次;
在这里，因为每个物品可以取任意多次，所以不再强求用上一轮的状态，即本轮放过的物品，在后面还可以再放;*/

多重背包I

每个物品最多取 s 次($O(n^3)$)

二维写法
for(int i = 1; i <= n; i ++){
    cin >> v >> w >> s;
    for(int j = 0; j <= m; j ++){
        for(int k = 0; k <= s && k * v <= j; k ++){
            f[i][j] = max(f[i][j], f[i - 1][j - v * k] + w * k); 
            // k = 0 已经包含了f [ i ] [ j ] = f [ i - 1 ] [ j ] 也就是不选 i 这个操作，
        }
    }
}



一维写法
for(int i = 1; i <= n; i ++){
    cin >> v >> w >> s;
    for(int j = m; j >= v; j --){
        for(int k = 0; k <= s && k * v <= j; k ++){
            f[j] = max(f[j], f[j - v * k] + w * k); 
        }
    }
}

多重背包II

每个物品最多取 s 次($O(n m logs)$)

$f[i,j] = max(f[i−1,j],f[i−1,j−v]+w,f[i−1,j−2v]+2w,…..f[i−1,j−Sv]+Sw)$

$f[i,j−v] = max(f[i−1,j−v],f[i−1,j−2v]+w,…..f[i−1,j−Sv]+(S−1)w,f[i−1,j−(S+1)v]+Sw)$

因为有次数 S 和 容量 j 的限制，最后一项并不能确定是否能装满，无法消除。

关于为什么不能像完全背包一样优化：关键在于完全背包问题仅有 v[i] k <= j 的限制，所以f(i, j) 与 f(i, j - v) 的最后一项都应满足背包能够装得下，f(i, j - v)由于容量上限限制，故两者的最后一项是相同的；而在多重背包中，还需要满足 k <= s[i]，当 s[i] v[i] <= j - v 时，可以将所有的物品 i 均放入也不会超出容量限制，故 f(i, j - v) 将会比 f(i, j)多一项。

水果店里有 40 个苹果，小明计划购买 n  ( 1 ≤ n ≤ 40 ) 个苹果，试问如何让小明尽可能快速地完成购买？
一个显而易见的暴力做法是，让小明一个个拿（单位是个），但效率过于低下。事实上，店员可事先准备好 6 个箱子，每个箱子中的苹果数量分别为[ 1 , 2 , 4 , 8 , 16 , 9 ]，再让小明按箱子拿（单位是箱子），无论小明计划购买多少个，他最多只需要拿 6 次，而在暴力做法中，小明最多需要拿 40 次。

二进制优化
int cnt = 0;
for(int i = 1; i <= n; i ++ ){
    int a, b, s;
    cin >> a >> b >> s;
    int k = 1;
    while(k <= s){ //二进制分组转化成01背包
        cnt ++ ;
        v[cnt] = a * k;
        w[cnt] = b * k;
        s -= k;
        k *= 2;
    }
    if(s > 0){
        cnt ++ ;
        v[cnt] = a * s;
        w[cnt] = b * s;
    }
}
n = cnt;
for(int i = 1; i <= n; i ++ ){
    for(int j = m; j >= v[i]; j -- ){
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}

分组背包

每组物品有若干个，同一组内的物品最多只能选一个。

for(int i = 1; i <= n; i ++ ){
    cin >> s[i];
    for(int j = 0; j < s[i]; j ++ ){
        cin >> v[i][j] >> w[i][j];
    }
}

for(int i = 1; i <= n; i ++ ){//01背包类似
    for(int j = m; j >= 0; j -- ){
        for(int k = 0; k < s[i]; k ++ ){
            if(j >= v[i][k])f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
        }
    }
}