多重背包简介

背包问题

背包问题是指在一个有容积限制(或者重量限制)的背包中放入物品,物品拥有体积、重量和价值等属性。需要求一种满足背包限制的放置物品的方式,使得背包中物品的价值之和最大。根据物品的限制条件可分为01背包、完全背包、多重背包和分组背包等问题。背包问题是动态规划的经典问题之一,在实际中往往有很多变形,需要通过一些方法,把问题转化为背包问题。


多重背包

多重背包的特点是物品的数量可以大于1但有限制。状态定义与01背包一致。多重背包的解法有多种,复杂度也不相同。可以将其转化为01背包求解(常用二进制优化),也可以用单调队列进行优化,有些情况下还可以用完全背包的方法进行状态转移。

基本转移: 背包大小V 物品件数n(每个物体有无数个) 第i个物品的花费c[i] 第i个物品的价值w[i] 第i个物品的上限数量max[i] 即在保证花费和不超过V的情况下,尽可能让价值最大 用dp[i][j]表示前i个物品在最大体积为j的情况下的最大价值(所求答案为dp[n][V]) 有dp[i][j] = max{ dp[i-1][ j - k * D[i] ] + k * D[i] , dp[i][j] } (0 <= k <= max[i]) 此时,时间复杂度为O(V*∑max[i])


采用二进制分解可以优化到O(V*∑log max[i]) 对于数量为0-n的物品i,可以将其分割成多个组合。 使得所有组合加起来能够等于n,并且选取一定量的组合可以组成0-n的任意数 一个数可以分成两个数,两个数相加可以得到这个数 而这两个数还能继续分成两个数 如果分成的两个数相等,则可以再下次分割只分其中一个 这样在保证尽可能少分的情况下分到最深就是需要的计算方法 对于一个最多有n个的物品,可以分成(近似)log(2)n个,然后对这些进行01背包求解 如果物品i的总体积大于背包体积,则不必再分割(在范围内没有上限可以看作无限)。


看下面这个例题


例题:HDU 2844

problem

大意:有n种硬币,每种硬币面值为A,数量为C。有一个物品的价格为<=M且>=1,问手表的价格(1~m)有多少种是可以在这些硬币中选出一些硬币恰好进行支付的?


思路

此题没有求最值,求的是可达状态数

定义dp[i]表示是否可以从这些硬币中选取一些硬币,使面值之和为i,dp[i]取值为1表示可以,取值为0表示不可以。定义转移方程为:

dp[i]=dp[i]  |  dp[i-A[i]]  | ... |  dp[i-A[i]*C[i]]
// |表示或运算  只要有一个为1  dp[i]即为1  即可以凑成

处理每种硬币时,每个状态要转移的次数与Ci有关,使得处理第i种硬币的复杂度为O(M*Ci),如果Ci比较大,则复杂度较高。可以采用二进制数的方法进行优化,使得每种物品的转移次数变为O(M * log(Ci))

方法是将第i种硬币分组,分别以1,2,4,... ,2^n个硬币为一组,这些数相加等于Ci。可知,任意小于等于Ci的数字都可以由这些数字组合而成。将每一组的硬币面值相加作为一个硬币来处理,就可以转化为01背包的问题来解决了。


代码示例

#include<bits/stdc++.h>
using namespace std;
int w[1005];
int dp[100010];
int a[101],c[101];

int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    while(cin>>n>>m&&(n+m))
    {
        for(int i=0;i<n;++i) cin>>a[i];//输入硬币价值
        for(int i=0;i<n;++i) cin>>c[i];//输入硬币数量
        int cnt=0,x;
        for(int i=0;i<n;++i){
            for(int j=1;c[i]>0;j*=2){//对每种硬币进行二进制分组
                x=min(j,c[i]);
                c[i]-=x;
                w[cnt++]=a[i]*x;//记录该分组的硬币价值之和
            }
        }
        memset(dp,0,sizeof(dp));//初始化所有状态不可达
        dp[0]=1;//初始化状态0位可达
        for(int i=0;i<cnt;++i){
            for(int j=m;j>=w[i];j--){
                if(dp[j-w[i]])//如果状态j-w[i]是可达的,则进行转移
                    dp[j]=1;
            }
        }
        int ans=0;
        for(int i=1;i<=m;++i){
            ans+=dp[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}




评论

登录之后就可以评论 / 回复啦(#^.^#)    点此登录    点此注册

评论列表

暂无评论!快写一条吧(๑′ᴗ‵๑)