背包问题

背包问题🎒

背包问题是DP（动态规划）中一类经典的问题，和其它DP问题一样，找到递推关系是关键❗❗

简单背包问题

题目描述：

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S。如果有满足条件的选择，则此背包有解，否则此背包问题无解。

输入样例

1
2
20 5 
1 3 5 7 9

输出样例

1
YES

🔑

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
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
    int s, n;
    int w[1005];
    bool dp[1005][1005];    // dp[i][j]: 前i件物品，能否正好凑出j的重量
    while (cin>>s>>n)
    {   
        for (int i = 1; i <= n; i++)
        {
            cin>>w[i];
        }
        memset(dp,0,sizeof(dp));
        dp[0][0] = true;	// 对于所有的dp[i][0] = true, 因为我只要一种物品都不选，就可以凑出0

        for (int i = 1; i <= n; i++)
        {
            for (int j = s; j >= 0; j--)
            {
                if(dp[i-1][j] == 1)   
                {// 如果前（i-1）件商品就可以凑出来，那么，前i件也可以凑出
                    dp[i][j] = 1;
                }
                if(j >= w[i] && dp[i-1][j-w[i]] == 1)
                {// 前（i-1）件商品凑出来的值+第i件商品的质量后，
                 // 背包中所有物品的重量就刚好等于j
                    dp[i][j] = 1;
                }
            }            
            
        }

        if(dp[n][s])
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
     
    }
    
    return 0;
}

完全背包问题

题目描述

有n种（每一种有无数个）重量和价值分别为Wi,Vi的物品，现从这些物品中挑选出总量不超过W的物品，求所有方案中价值总和的最大值。

输入样例

1
输入包含多组测试用例，每一例的开头为两位整数 n、W（1<=n<=10000,1<=W<=1000），接下来有 n 行，每一行有两位整数 Wi、Vi（1<=Wi<=10000,1<=Vi<=100）
1
2
3
4
5
6
7
8
3 4
1 2
2 5
3 7
3 5
2 3
3 4
4 5

输出样例

1
输出为一行，即所有方案中价值总和的最大值。
1
2
10
7

🔑

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int s, n;
    int w[10005], v[10005];
    int dp[10005]; // dp[i]: 重量不超过i时，能装下的最大价值
    while (cin >> n >> s)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> w[i] >> v[i];
        }
        memset(dp, 0, sizeof(dp));        

        for (int i = 1; i <= n; i++)
        {
            for (int j = w[i]; j <= s; j++)
            {
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        cout << dp[s] << endl;
        
    }

    return 0;
    
}

Buyer

这一题与第二题很像，但是有差别：这里每种物品只能选一次放到包里，而上面那题每种物品有无数个，可以重复选。而且这题不仅需要求最优解，还要输出具体的解法。

问题描述

哆啦A梦班级举办个party，当然吃的东西必不可少，哆啦A梦负责采购任务，他得到了一份清单，上面注明不同食品的受欢迎程度，哆啦A梦需要用一定的价钱尽可能达到的更大的受欢迎程度！例如，瓜子的受欢迎程度为20，瓜子的价钱是50元，那么如果哆啦A梦选择买瓜子，将花费50元，但受欢迎程度增加了20。为了避免食品单调性，每种食品只能买一份，不能重复购买。 现在哆啦A梦需要知道如何采购才能达到最大的受欢迎程度，你能帮助他吗？

输入样例

1
输入数据为多组，每组输入的第一行有两个正整数M和N(M<100&&N<1000)，分别为哆啦A梦可以支配的钱数和清单上的可选择的物品种类。 接下来的N行每行有两个正整数,分别为每种物品的价钱和它的受欢迎程度（编号为1到N）。
1
2
3
4
5
10 4
100 5
5 5
5 5
10 10

输出样例

1
如果存在物品购买，那么输出的第一行为能够达到的最大的受欢迎程度。第二行为需要购买的物品的编号（如果有多种可能，输出字典序靠前的那种），空格分隔每个数字；如没有物品可以购买，输出只有一行，为数字0。
1
2
10
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
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int main()
{
    int money, items;
    int price[1005], happy[1005];
    int dp[200][200]; // dp[i]: 价格不超过i时，能获得的最大快乐值

    while (cin >> money >> items)
    {
        for (int i = 1; i <= items; i++)
        {
            cin >> price[i] >> happy[i];
        }
        memset(dp, 0, sizeof(dp));

        for (int i = 1; i <= items; ++i)
        {
            for (int j = 0; j <= money; ++j)
            {
                if (j < price[i])
                {
                    dp[i][j] = dp[i - 1][j];
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - price[i]] + happy[i]);
                }
            }
        }
        cout << dp[items][money];
        if (dp[items][money] != 0)
            cout << endl;

        int j = money;
        for (int i = items; i > 0; i--)
        {
            if (dp[i][j] != dp[i - 1][j]) 
            {// 当两者不等时，说明我选择了第i件物件
                cout << i << " ";
                j -= price[i];
            }
        }

        cout << endl;
    }

    return 0;
}
笔记
算法 DP

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！