背包

01 背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<iostream>
#include<cstring>
using namespace std;

const int N=20020;
const int M=50;

int dp[N];
int v[M];
int w[M];

int main()
{
    int V,n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=v[i];j--)    //从后往前
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V]<<endl;
    return 0;
}

完全背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include<iostream>
using namespace std;

const int N=1e7+10;

int dp[N];
int v[N];//体积
int w[N];//价值

int main()
{
    int T;
    cin>>T;
    int n,V;
    cin>>n>>V;

    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>w[i];
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=v[i];j<=V;j++)    //从一个v[i]开始j++
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }

    cout<<dp[V]<<endl;
    return 0;
}

多重背包

二进制拆分，转化为 01 背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;

const int N=1010;   //N≈nlogs

int dp[N];
int v[N];
int w[N];

int main()
{
    int n,V;
    cin>>n>>V;
    int cnt=0;

    for(int i=1;i<=n;i++)
    {
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        while (k<=s)
        {
            cnt++;
            v[cnt]=k*a;
            w[cnt]=k*b;
            s-=k;
            k*=2;
        }

        if(s>0)
        {
            cnt++;
            v[cnt]=s*a;
            w[cnt]=s*b;
        }
        
    }
        for(int i=1;i<=cnt;i++)
        {
            for(int j=V;j>=v[i];j--)
            {
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
            }
        }

        cout<<dp[V]<<endl;

        return 0;
}

分组背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
using namespace std;

const int N=110;

int dp[N];
int v[N][N];//体积
int w[N][N];//价值
int s[N];


int main()
{
    int n,V;
    cin>>n>>V;

    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=1;j<=s[i];j++)
        {
            cin>>v[i][j]>>w[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=V;j>=0;j--)
        {
            for(int k=1;k<=s[i];k++)//第i个组中的第k个物品
            {
                if(j>=v[i][k])
                {
                    dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
                }
            }
        }
    }

    cout<<dp[V]<<endl;
    return 0;
}