算法【混合背包】

发布于:2025-02-10 ⋅ 阅读:(36) ⋅ 点赞:(0)

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

下面通过题目加深理解。

题目一

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


网站公告

今日签到

点亮在社区的每一天
去签到