0-1背包

一.01背包

划重点：当一件物品只能用一次时，必须要在同一个背包循环中只放一次，所以要容量倒走，根据递推表达式也可以知道

例题1：

https://www.luogu.org/problemnew/show/P1060

普通版：

每件物品之能拿一次，有拿和不拿俩种状态

dp(i,j)表示拿到i件物品时，j容量下价值的最大值

空间够用：判断价值决定拿不拿 dp[j][i] = max(dp[j-1][i],dp[j-1][i - th[j].m]+th[j].m*th[j].v);

空间不够用：只有不拿 dp[j][i] = dp[j-1][i];

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
/*-------------------------------------------------------------------------------------------*/
struct BAG
{
    int m;
    int v;
}th[25];
int dp[25][MAX];
/* ------------------------------------------------------------------------------------------*/

int main()
{
    //std::ios::sync_with_stdio(false);
    cin >> M >> N;
    for(int i =1;i <= N;i++)
    {
        cin >> th[i].m >> th[i].v;
    }
    for(int j = 1;j <= N;j++)
    {
        for(int i = 1;i <= M;i++)
        {
            if(th[j].m <= i)
            {
                dp[j][i] = max(dp[j-1][i],dp[j-1][i - th[j].m]+th[j].m*th[j].v);
            }
            else
            {
                dp[j][i] = dp[j-1][i];
            }
        }
    }
    cout << dp[N][M] << "\n";
    return 0;
}
优化空间：

（不是这个题的，只是空间优化了，没有加权值而已，一毛一样）

https://www.luogu.org/problemnew/show/P1049

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
/*-------------------------------------------------------------------------------------------*/
int a[MAX_1];
int dp[MAX];
/* ------------------------------------------------------------------------------------------*/

int main()
{
    //std::ios::sync_with_stdio(false);
    cin >> M >> N;
    for(int i = 0;i <= MAX;i++)
    {
        dp[i] = i;
    }
    for(int i =1;i <= N;i++)
    {
        cin >> a[i];
    }
    for(int j = 1;j <= N;j++)
    {
        for(int i = M;i >= 1;i--)
        {
            if(a[j] <= i)
            {
                dp[i] = min(dp[i],dp[i-a[j]]);
                //cout << i << ":" << dp[i-a[j]] << " " << dp[i] <<endl;
            }
        }
    }
    cout << dp[M] << "\n";
    return 0;
}

例题2：

https://www.luogu.org/problemnew/show/P1164

这个题需要背包恰好装满

把dp初始化为INF，当 当前的物品不能恰好装满的时候，就为非法值

dp[i]存储的为，背包容量为i的时候恰好装满的方案数，不存在为INF

dp[0] = 1;递推；

1.装不下不装

2.装下但不是恰好装满，不装

3.恰好装满

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
/*-------------------------------------------------------------------------------------------*/
int a[MAX_1];
int dp[MAX];
/* ------------------------------------------------------------------------------------------*/

int main()
{
    //std::ios::sync_with_stdio(false);
    cin >> N >> M;
    for(int i = 1;i <= MAX;i++)
    {
        dp[i] = INF;
    }
    dp[0] = 1;
    for(int i =1;i <= N;i++)
    {
        cin >> a[i];
    }
    //dp[a[1]] = 1;
    for(int j = 1;j <= N;j++)
    {
        for(int i = M;i >= 1;i--)
        {
            if(a[j] <= i)
            {
                if(dp[i - a[j]] != INF)
                {
                    if(dp[i] == INF)
                    {
                        dp[i] = dp[i - a[j]];
                    }
                    else dp[i] += dp[i - a[j]];

                }
            }
        }
    }
    cout << dp[M] << "\n";
    return 0;
}

此题有待寻找更好的递推

二.完全背包

容量正走

https://www.luogu.org/problemnew/show/P1616

没什么不同啊，就是把容量正的走而已了，一件物品放一次放一次放一次

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
/*-------------------------------------------------------------------------------------------*/
struct YAO
{
    int t;
    int v;
}a[MAX_1];
int dp[MAX];
/* ------------------------------------------------------------------------------------------*/

int main()
{
    //std::ios::sync_with_stdio(false);
    cin >> M >> N;
    for(int i =1;i <= N;i++)
    {
        cin >> a[i].t >> a[i].v;
    }
    for(int i = 1;i <= M;i++)
    {
        for(int j = 1;j <= N;j++)
        {
            if(a[j].t <= i)
            {
                dp[i] = max(dp[i],dp[i-a[j].t]+a[j].v);
            }
        }
    }
    cout << dp[M] << "\n";
    return 0;
}

三.多重背包

听说是：三重循环

还没做题呢，等着吧

完全背包的恰好装满

多重背包的俩种没做

四.变形背包

https://www.luogu.org/problemnew/show/P1064

数据读入做了下处理，减少循环

使用了vector记录每个主件有几个附件

题意说了，最多俩个

dp[i]当然是最大的价值

那么我们的状态转移就有4个

一个主件

一主一副1

一主一副2

一主俩副

转移就完事了

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
50
51
52
53
54
55
56
57
58
59
60
61
62
/*-------------------------------------------------------------------------------------------*/
struct YAO
{
    int m;
    int v;
    YAO(int mm,int vv) : m(mm),v(vv){}
};
vector<vector<YAO> > a(MAX_1);
int dp[MAX];
/* ------------------------------------------------------------------------------------------*/

int main()
{
    //std::ios::sync_with_stdio(false);
    cin >> M >> N;
    M /= 10;
    for(int i =1;i <= N;i++)
    {
        int x,y,z;
        cin >>x >>y>>z;
        if(z == 0)
        {
            a[i].push_back(YAO(x/10,y));
        }
        else
        {
            a[z].push_back(YAO(x/10,y));
        }
    }

    for(int i = 1;i <= N;i++)
    {
        if(a[i].size() == 0) continue;
        for(int j = M;j >= 1;j--)
        {
            if(j >= a[i][0].m)
            {
                dp[j] = max(dp[j],dp[j - a[i][0].m]+a[i][0].m*a[i][0].v);
            }
            if(a[i].size() > 1)
            {
                if(j >= a[i][0].m + a[i][1].m)
                {
                    dp[j] = max(dp[j],dp[j - a[i][0].m - a[i][1].m]+a[i][0].m*a[i][0].v+a[i][1].m*a[i][1].v);
                }
                if(a[i].size() > 2)
                {
                    if(j >= a[i][0].m + a[i][2].m)
                    {
                        dp[j] = max(dp[j],dp[j - a[i][0].m - a[i][2].m]+a[i][0].m*a[i][0].v+a[i][2].m*a[i][2].v);
                    }
                    if(j >= a[i][0].m + a[i][1].m +a[i][2].m)
                    {
                        dp[j] = max(dp[j],dp[j - a[i][0].m - a[i][1].m - a[i][2].m]+a[i][0].m*a[i][0].v+a[i][2].m*a[i][2].v + a[i][1].m*a[i][1].v);
                    }
                }
            }
        }
    }
    cout << dp[M]*10 << "\n";
    return 0;
}