算法【混合背包】

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

下面通过题目加深理解。

题目一

测试链接：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;
}