混合背包是指多种背包模型的组合与转化。

下面通过题目加深理解。

题目一

测试链接：1742 -- Coins

分析：这道题可以通过硬币的个数将其转化为01背包，完全背包和多重背包。如果硬币的个数是1个，则是01背包；如果硬币的面值×硬币的个数大于当前需要找零的数额，则是完全背包；否则是多重背包。对于不同的背包进行不同的可能性展开，最后统计，即可得到答案。代码如下。

#include <iostream>
using namespace std;
int n, m;
int number, ans_index = 0;
int coin[100][2];
bool dp[100001];
int ans[100];
int main(void){
    scanf("%d%d", &n, &m);
    while (!(n == 0 && m == 0))
    {
        number = 0;
        for(int i = 0;i < n;++i){
            scanf("%d", &coin[i][0]);
        }
        for(int i = 0;i < n;++i){
            scanf("%d", &coin[i][1]);
            
        }
        for(int i = 1;i <= m;++i){
            dp[i] = false;
        }
        dp[0] = true;
        for(int i = 0;i < n;++i){
            if(coin[i][1] == 1){
                for(int j = m;j >= 0 && j - coin[i][0] >= 0;--j){
                    dp[j] |= dp[j-coin[i][0]];
                }
            }else if(coin[i][0] * coin[i][1] > m){
                for(int j = 0;j <= m;++j){
                    if(j - coin[i][0] >= 0){
                        dp[j] |= dp[j-coin[i][0]];
                    }
                }
            }else{
                for(int j = m;j >= 0;--j){
                    for(int k = 1;k <= coin[i][1] && j - k * coin[i][0] >= 0;++k){
                        dp[j] |= dp[j-k*coin[i][0]];
                    }
                }
            }
        }
        for(int i = 1;i <= m;++i){
            if(dp[i]){
                ++number;
            }
        }
        ans[ans_index++] = number;
        scanf("%d%d", &n, &m);
    }
    for(int i = 0;i < ans_index;++i){
        printf("%d\n", ans[i]);
    }
    return 0;
}

其中，求dp数组循环中，i为在下标0~i的物品中取。当然，这道题其实可以直接将其当作一个多重背包，二进制优化后转化为01背包进行求解。代码如下。

#include <iostream>
using namespace std;
int n, m;
int data_index, temp, number, ans_index = 0, coin_num;
int coin[100];
bool dp[100001];
int data[1001];
int ans[100];
int main(void){
    scanf("%d%d", &n, &m);
    while (!(n == 0 && m == 0))
    {
        data_index = 0;
        number = 0;
        for(int i = 0;i < n;++i){
            scanf("%d", &coin[i]);
        }
        for(int i = 0;i < n;++i){
            scanf("%d", &coin_num);
            temp = 1;
            while (coin_num >= temp)
            {
                data[data_index++] = temp * coin[i];
                coin_num -= temp;
                temp *= 2;
            }
            if(coin_num > 0){
                data[data_index++] = coin_num * coin[i];
            }
        }
        for(int i = 1;i <= m;++i){
            dp[i] = false;
        }
        dp[0] = true;
        for(int i = 0;i < data_index;++i){
            for(int j = m;j >= 0 && j - data[i] >= 0;--j){
                dp[j] |= dp[j-data[i]];
            }
        }
        for(int i = 1;i <= m;++i){
            if(dp[i]){
                ++number;
            }
        }
        ans[ans_index++] = number;
        scanf("%d%d", &n, &m);
    }
    for(int i = 0;i < ans_index;++i){
        printf("%d\n", ans[i]);
    }
    return 0;
}