首页 > 代码库 > 背包的自我修养

背包的自我修养

2024-07-11 18:01:00   226人阅读

大概了解了背包九讲前面四章的内容。先 ORZ DD大神一分钟……59，58，57……


……3，2，1。好，结束，总结一下三种背包问题，01，完全，多重。都隶属于动态规划问题。


下面这是个人四天来的学习体会。

区别方式也很简单：


①物品数量只有一个，只存在放和不放的区别，01背包。

②物品数量有无限多个，或者能完全把背包装满，完全背包。

③物品数量有限而且不能把背包装满。多重背包。


这也是在选择策略时的调用条件。


我们这样来表示：

int n,m;
//物品种类 和 背包容量
int dp[10001];
//背包不同状态的价值
int cost[1001],value[1001],cot[1001];
//费用，价值，数量


当 cot[i]==1的时候，只存在放或者不放，这时候就选择01背包策略。

if(cot[i]==1)
                zeroonepack(cost[i],value[i]);

当cost[i]*cot[i]>=m的时候，表明比能装满包还多，就用完全背包策略。

else if(cot[i]*cost[i]>=m)
                completepack(cost[i],value[i]);

剩下情况就使用 多重背包策略。

else
                multiplepack(cost[i],value[i],cot[i]);


这几种策略，我前面的解题报告提过，现在都写出来。


01背包的情况：


void zeroonepack(int cost,int value)
{
    for(int i=m;i>=cost;i--)
        dp[i]=max(dp[i],dp[i-cost]+value);
}
//01背包

从 m->0 保证是由上一状态得来。


完全背包：


void completepack(int cost,int value)
{
    for(int i=cost;i<=m;i++)
        dp[i]=max(dp[i],dp[i-cost]+value);
}
//完全背包

从 0->m 由于物品无限多，放了之后还能放，就不像01一样，必须选择下个物品。也就不用倒过来保证选择状态。


多重背包：


void multiplepack(int cost,int value,int cot)
{
    int k=1;
    while(k<cot)
    {
        zeroonepack(cost*k,value*k);
        cot-=k;
        k<<1;
    }
    zeroonepack(cost*cot,value*cot);
}
//多重背包

不能装满背包，最基本的思想就是把每个物品进行01背包，不过要是物品超过100万，甚至更大呢？

这时候就要分解物品。但是又要保证 小于 其数量的 都 尝试装过。需要用二进制的策略以减少时间复杂度。

比如 17 个物品，分解成 1，2，4，8，（17-8-4-2-1）=2；

分解后的五个物品分别为：1，2，2，4，8。

如果选择 比 17 小的物品装包 分别为：

1=1；

2=2；

3=2+1；

4=2+2；

5=2+2+1；

6=4+2；

7=4+2+1；

……

17=1+2+2+4+8；

这样不会存在遗漏选择 某个数量的物品装包 的可能性。

然后把分组后的 五个物品 进行01背包。



最后贴上大概可以通用的代码：


#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
using namespace std;

int n,m;
//物品种类 和 背包容量
int dp[10001];
//背包不同状态的价值
int cost[1001],value[1001],cot[1001];
//费用，价值，数量
void zeroonepack(int cost,int value)
{
    for(int i=m;i>=cost;i--)
        dp[i]=max(dp[i],dp[i-cost]+value);
}
//01背包
void completepack(int cost,int value)
{
    for(int i=cost;i<=m;i++)
        dp[i]=max(dp[i],dp[i-cost]+value);
}
//完全背包
void multiplepack(int cost,int value,int cot)
{
    int k=1;
    while(k<cot)
    {
        zeroonepack(cost*k,value*k);
        cot-=k;
        k<<1;
    }
    zeroonepack(cost*cot,value*cot);
}
//多重背包
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%d%d%d",&cost[i],&value[i],&cot[i]);

        memset(dp,0,sizeof(dp));

        for(int i=0;i<n;i++)
        {
            if(cot[i]==1)
                zeroonepack(cost[i],value[i]);
            else if(cot[i]*cost[i]>=m)
                completepack(cost[i],value[i]);
            else
                multiplepack(cost[i],value[i],cot[i]);
        }
        int ans=0;
        for(int i=0;i<=m;i++)
            //printf("%d ==\n",dp[i]);
        ans=max(ans,dp[i]);
        printf("%d\n",ans);
    }
}


至于背包九讲后面的五个内容，咱还是觉得体会一下就好，不深入了。

接下来就是没看完的图论了，网络流！我来了……


联系
我们