普通背包 完全背包 多重背包 分組背包

背包問題

還有一個依賴背包暫時沒學，基礎dp應該用不到吧……

1.普通背包

已知 n n n件物品的體積和價值，每一件最多用一次，總體積不能超過 v o l vol vol，問最大價值

核心代碼： d p [ v o l ] dp[vol] dp[vol]即為答案

for (int i=1;i<=n;i++)
{
    for (int j=vol;j>=p[i].w;j--)
    {
        dp[j]=max(dp[j],dp[j-p[i].w]+p[i].val);
    }
}
           

2.完全背包

已知 n n n件物品的體積和價值，每一件可以随便用，總體積不能超過 v o l vol vol，問最大價值

核心代碼： d p [ v o l ] dp[vol] dp[vol]即為答案

for (int i=1;i<=n;i++)
{
    for (int j=p[i].w;j<=vol;j++)
    {
        dp[j]=max(dp[j],dp[j-p[i].w]+p[i].val);
    }
}
           

3.多重背包

已知 n n n件物品的體積和價值和數量，總體積不能超過 v o l vol vol，問最大價值

核心代碼： d p [ v o l ] dp[vol] dp[vol]即為答案

for (int i=1;i<=n;i++)
{
    for (int j=0;j<p[i].num;j++)
    {
        for (int k=vol;k>=p[i].w;k--)
        {
            dp[k]=max(dp[k],dp[k-p[i].w]+p[i].val);
        }
    }
}
           

4.分組背包

已知物品的價值和體積，分成 K K K個組，每個組隻能最多取一件，總體積不能超過 v o l vol vol，問最大價值

核心代碼： d p [ v o l ] dp[vol] dp[vol]即為答案

for (int i=1;i<=K;i++)//每個組
{
    for (int k=vol;k>=0;k--)
    {
        for (int j=0;j<group[i].size();j++)
        //每個組裡面每一個物品，用vector或者數組存
        {
            int x=group[i][j];
            if (k>=w[x])
            {
                dp[k]=max(dp[k],dp[k-w[x]]+val[x]);
            }
        }
    }
}
           

例題1

HDU1171

其實每一個多重背包也可以看成是普通背包來做，把具有多個數量的物品拆成很多個單一物體就可以了，這個思想叫啥也說不上來

大緻題意：一共有N組資料，包含裝置的價值和數量，把這些裝置均分，使得分成的兩堆價值差異盡量小

分析：先求出裝置總價值量 s u m = ∑ （ w [ i ] ∗ n u m [ i ] ） sum=\sum（w[i]*num[i]） sum=∑（w[i]∗num[i]），然後在體積為 s u m / 2 sum/2 sum/2的背包中求就可以了

做法1:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<queue>
#include<map>
#define ll long long
#define pb push_back
#define rep(x,a,b) for (int x=a;x<=b;x++)
#define repp(x,a,b) for (int x=a;x<b;x++)
#define mem(a,x) memset(a,x,sizeof a)
using namespace std;
const int maxn=2e6+7;
int dp[maxn],n,x,y;
vector<int >v;
int main()
{
    while(~scanf("%d",&n)&&n>-1)
    {
        int sum=0;
        mem(dp,0);
        v.clear();
        rep(i,1,n)
        {
            scanf("%d%d",&x,&y);
            sum+=x*y;
            while(y--)v.pb(x);
        }
        int sum1=sum/2;
        for (int i=0;i<v.size();i++)
        {
            for (int j=sum1;j>=v[i];j--)
            {
                dp[j]=max(dp[j],dp[j-v[i]]+v[i]);
            }
        }
        cout<<max(dp[sum1],sum-dp[sum1])<<" "<<min(dp[sum1],sum-dp[sum1])<<endl;
    }
    return 0;
}
           

做法2：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<queue>
#include<map>
#define ll long long
#define pb push_back
#define rep(x,a,b) for (int x=a;x<=b;x++)
#define repp(x,a,b) for (int x=a;x<b;x++)
#define mem(a,x) memset(a,x,sizeof a)
using namespace std;
const int maxn=2e6+7;
int dp[maxn],n,x,y;
struct node
{
    int x;
    int num;
} p[maxn];
int main()
{
    while(~scanf("%d",&n)&&n>-1)
    {
        mem(dp,0);
        int sum=0;
        rep(i,1,n)
        {
            scanf("%d%d",&x,&y);
            p[i].x=x;
            p[i].num=y;
            sum+=x*y;
        }
        for (int i=1; i<=n; i++)
        {
            for (int j=0; j<p[i].num; j++)
            {
                for (int k=sum/2; k>=p[i].x; k--)
                {
                    dp[k]=max(dp[k],dp[k-p[i].x]+p[i].x);
                }
            }
        }
        cout<<max(dp[sum/2],sum-dp[sum/2])<<" "<<min(dp[sum/2],sum-dp[sum/2])<<endl;
    }
    return 0;
}
           

例題2

P1164 小A點菜

雖然也是背包問題，但需要進一步的了解

大緻題意：給出N個菜，兜裡有M塊錢，問有多少種買菜方案，使得錢剛好花完。

根據題目的資料，可以枚舉在位置i剩餘 x ( 1 ≤ x ≤ m ) x(1\leq x \leq m) x(1≤x≤m)塊錢的情形，買或者不買為轉移條件

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<queue>
#include<map>
#define ll long long
#define pb push_back
#define rep(x,a,b) for (int x=a;x<=b;x++)
#define repp(x,a,b) for (int x=a;x<b;x++)
#define W(x) printf("%d\n",x)
#define WW(x) printf("%lld\n",x)
#define pi 3.14159265358979323846
#define mem(a,x) memset(a,x,sizeof a)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
const int maxn=1e4+7;
const int INF=1e9;
const ll INFF=1e18;
ll dp[101][maxn],a[maxn],n,m,ans=0;
int main()
{
    scanf("%lld%lld",&n,&m);
    rep(i,1,n)scanf("%lld",&a[i]);
    mem(dp,0);
    dp[1][m]=1;
    if (m>=a[1])dp[1][m-a[1]]=1;
    rep(i,2,n)
    {
        rep(j,1,m)
        {
            if (j>=a[i])dp[i][j-a[i]]+=dp[i-1][j];
            dp[i][j]+=dp[i-1][j];
        }
    }
    rep(i,1,n)ans+=dp[i][0];
    WW(ans);
}
           

例題3

P1616 瘋狂的采藥

多重背包模闆題