【动态规划-背包模型part5（背包问题方案数量、有有依赖的背包问题、贪心+dp）】：背包问题求具体方案数、有依赖的背包问题、能量石、金明的预算方案【已更新完成】_背包问题输出装入背包的物品编号

---

1、背包问题求具体方案数

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi ，价值是 wi 。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 字典序最小的方案。这里的字典序是指：所选物品的编号所构成的序列。物品的编号范围是 1…N 。

> 输入格式 第一行两个整数，N，V ，用空格隔开，分别表示物品数量和背包容积。
> 
> 接下来有 N  行，每行两个整数 vi,wi ，用空格隔开，分别表示第 i  件物品的体积和价值。
> 
> 输出格式
> 输出一行，包含若干个用空格隔开的整数，表示最优解中所选物品的编号序列，且该编号序列的字典序最小。
> 
> 物品编号范围是 1…N 。
> 
> 数据范围
> 0<N,V≤1000
> 
> 0<vi,wi≤1000
> 输入样例
> 
>4 5 
>1 2 
>2 4 
>3 4 
>4 6
> 
> 输出样例： 
> 1 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路：

01背包+背包dp输出方案
为了输出背包dp方案，我们可以把整个状态转移的过程看成一个拓扑图

可以从最后一个状态倒推到初始状态，就可以输出方案了：

    for (int i = 1, j = m; i <= n; ++ i)
    {
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            path[cnt ++ ] = i;
            j -= v[i];
        }
    }
    for (int i = 0; i < cnt; ++ i) cout << path[i] << " ";
1
2
3
4
5
6
7
8
9

代码：

#include <iostream>

using namespace std;

const int N = 1010;

int n, m;
int w[N], v[N];
int f[N][N];
int path[N], cnt;

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i];
    for (int i = n; i >= 1; -- i)
    {
        for (int j = 0; j <= m; ++ j)
        {
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    }
    for (int i = 1, j = m; i <= n; ++ i)
    {
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i])
        {
            path[cnt ++ ] = i;
            j -= v[i];
        }
    }
    for (int i = 0; i < cnt; ++ i) cout << path[i] << " ";
    cout << 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

---

2、有依赖的背包问题

有 N 个物品和一个容量是 V 的背包。

物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。

如下图所示：

如果选择物品5，则必须选择物品1和2。这是因为2是5的父节点，1是2的父节点。

每件物品的编号是 i ，体积是 vi ，价值是 wi ，依赖的父节点编号是 pi 。物品的下标范围是 1…N 。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

> 
>输入格式 第一行有两个整数 N，V ，用空格隔开，分别表示物品个数和背包容量。
> 
> 接下来有 N  行数据，每行数据表示一个物品。 第 i  行有三个整数 vi,wi,pi
> ，用空格隔开，分别表示物品的体积、价值和依赖的物品编号。 如果 pi=−1 ，表示根节点。 数据保证所有物品构成一棵树。
> 
> 输出格式 输出一个整数，表示最大价值。
> 
> 
> 数据范围 1≤N,V≤100
> 
> 1≤vi,wi≤100 父节点编号范围：
> 
> 内部结点：1≤pi≤N;
> 
> 根节点 pi=−1;
> 
> 输入样例 
5 7 
2 3 -1 
2 2 1 
3 5 1 
4 7 2 
3 6 2
> 输出样例： 11  
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

思路：

dfs在遍历到 v[x] 结点时，一定选上根节点 x ，所以初始化 f[x][v[x] ~ m] = w[x]

j 的范围 [ v[x],m] 因为要放下根节点
k 的范围 [ 0 , j-v[x] ]，也因为要放下根节点

f[x][v]表达选择以x为子树的物品，在体积不超过v时所获得的最大价值

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=103;

const int V=103;

int w[N],v[N];

vector<int>g[N];

int n,m,root;

int f[N][N];

void dfs(int x)
{
	for(int i=v[x];i<=m;i++)f[x][i]=w[x];
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		dfs(y);
		for(int j=m;j>=v[x];j--)
		{
			for(int k=0;k<=j-v[x];k++)
			{
				f[x][j]=max(f[x][j],f[x][j-k]+f[y][k]);
			}
		}
	}
}

int main()
{
	cin>>n>>m;
	
	for(int i=1;i<=n;i++)
	{
		int father;
		cin>>v[i]>>w[i]>>father;
		if(father==-1)root=i;
		else g[father].push_back(i);
	}
	
	dfs(root);
	
	cout<<f[root][m];

    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
43
44
45
46
47
48
49
50
51
52

---

3、能量石

岩石怪物杜达生活在魔法森林中，他在午餐时收集了 N 块能量石准备开吃。

由于他的嘴很小，所以一次只能吃一块能量石。

能量石很硬，吃完需要花不少时间。

吃完第 i 块能量石需要花费的时间为 Si 秒。

杜达靠吃能量石来获取能量。

不同的能量石包含的能量可能不同。

此外，能量石会随着时间流逝逐渐失去能量。

第 i 块能量石最初包含 Ei 单位的能量，并且每秒将失去 Li 单位的能量。

当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。

能量石中包含的能量最多降低至 0 。

请问杜达通过吃能量石可以获得的最大能量是多少？

> 输入格式 第一行包含整数 T ，表示共有 T  组测试数据。
> 
> 每组数据第一行包含整数 N ，表示能量石的数量。
> 
> 接下来 N  行，每行包含三个整数 Si,Ei,Li 。
> 
> 输出格式 每组数据输出一个结果，每个结果占一行。
> 
> 结果表示为 Case #x: y，其中 x  是组别编号（从 1  开始），y  是可以获得的最大能量值。
> 
> 数据范围 1≤T≤10 , 1≤N≤100 , 1≤Si≤100 , 1≤Ei≤105 , 0≤Li≤105
 输入样例： 
 3 
 4 
 20 10 1 
 5 30 5 
 100 30 1 
 5 80 60 
 3 
 10 4 1000 
 10 3 1000 
 10 8 1000 
 2 
 12 300 50
 5 200 0 
输出样例：
 Case #1: 105 
 Case #2: 8 
 Case #3: 500 
 样例解释 在样例＃1中，有 N=4 个宝石。杜达可以选择的一个吃石头顺序是：
> 
> 吃第四块石头。这需要 5  秒，并给他 80  单位的能量。 吃第二块石头。这需要 5  秒，并给他 5  单位的能量（第二块石头开始时具有
> 30  单位能量，5  秒后失去了 25  单位的能量）。 吃第三块石头。这需要 100  秒，并给他 20 
> 单位的能量（第三块石头开始时具有 30  单位能量，10  秒后失去了 10  单位的能量）。 吃第一块石头。这需要 20  秒，并给他 0
> 单位的能量（第一块石头以 10  单位能量开始，110  秒后已经失去了所有的能量）。 他一共获得了 105 
> 单位的能量，这是能获得的最大值，所以答案是 105 。
> 
> 在样本案例＃2中，有 N=3  个宝石。
> 
> 无论杜达选择吃哪块石头，剩下的两个石头的能量都会耗光。
> 
> 所以他应该吃第三块石头，给他提供 8  单位的能量。
> 
> 在样本案例＃3中，有 N=2  个宝石。杜达可以：
> 
> 吃第一块石头。这需要 12  秒，并给他 300  单位的能量。 吃第二块石头。这需要 5  秒，并给他 200 
> 单位的能量（第二块石头随着时间的推移不会失去任何能量！）。 所以答案是 500 。

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

思路：

dp+贪心

参考贪心问题：耍杂技的牛，贪心类型一样

我们要证明我们有一种吃法一定最优
从最优的吃法里开始dp而不是枚举所有的吃法然后dp

代码：

为了便于理解，先看二维dp：

#include<bits/stdc++.h>

using namespace std;

const int N=103;
const int S=10005;

int n;

struct node
{
    int s,e,l;
};

node a[N];

int f[N][S];//前i个物品，总时间不超过j所获取的最大能量

bool cmp(node a,node b)
{
    return a.s*b.l < b.s*a.l;
}

int main()
{
    int t;
    cin>>t;
    int cnt=0;
    while(t--)
    {
        memset(f, -0x3f, sizeof f);//恰好的条件：全部初始化为负无穷
        int time=0;
        
        cin>>n;

        for(int i=1;i<=n;i++)
        {
            int s,e,l;
            cin>>s>>e>>l;
            time+=s;
            a[i]={s,e,l};
        }//读入数据，算出总时间time
        
        sort(a+1,a+n+1,cmp);//检查半天的原因：这里的a+n+1忘记+1了！！！！！！！！！！
		//真是气死人 
        
        //选前i个，总时间为0的方案数状态都是0 
		//for(int i=1;i<=n;i++)f[i][0]=0;
		f[0][0]=0;
        //开始使用背包
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=time;j++)
            {
                f[i][j]=f[i-1][j];//不选第i个
                if(j>=a[i].s)f[i][j]=max(f[i][j],f[i-1][j-a[i].s]+max(0,a[i].e-a[i].l*(j-a[i].s)));//加上的是流失后的能量
                //因为是恰好的情况 所以说j-a[i]就是吃前面石头消耗的能量
            }
        }
        int res=0;
        
        for(int i=1;i<=time;i++)res=max(f[n][i],res);//前n个物品中选择每种状态中最大的 

        printf("Case #%d: %d\n",++cnt,res);
    }

    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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

优化为一维01背包：

#include<bits/stdc++.h>

using namespace std;

const int N=103;
const int S=10005;

int n;

struct node
{
    int s,e,l;
};

node a[N];

int f[N][S];//前i个物品，总时间不超过j所获取的最大能量

bool cmp(node a,node b)
{
    return a.s*b.l < b.s*a.l;
}

int main()
{
    int t;
    cin>>t;
    int cnt=0;
    while(t--)
    {
        memset(f, -0x3f, sizeof f);//恰好的条件：全部初始化为负无穷
        int time=0;
        
        cin>>n;

        for(int i=1;i<=n;i++)
        {
            int s,e,l;
            cin>>s>>e>>l;
            time+=s;
            a[i]={s,e,l};
        }//读入数据，算出总时间time
        
        sort(a+1,a+n+1,cmp);//检查半天的原因：这里的a+n+1忘记+1了！！！！！！！！！！
		//真是气死人 
        
        //选前i个，总时间为0的方案数状态都是0 
		//for(int i=1;i<=n;i++)f[i][0]=0;
		f[0][0]=0;
        //开始使用背包
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=time;j++)
            {
                f[i][j]=f[i-1][j];//不选第i个
                if(j>=a[i].s)f[i][j]=max(f[i][j],f[i-1][j-a[i].s]+max(0,a[i].e-a[i].l*(j-a[i].s)));//加上的是流失后的能量
                //因为是恰好的情况 所以说j-a[i]就是吃前面石头消耗的能量
            }
        }
        int res=0;
        
        for(int i=1;i<=time;i++)res=max(f[n][i],res);//前n个物品中选择每种状态中最大的 

        printf("Case #%d: %d\n",++cnt,res);
    }

    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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

---

4、金明的预算方案

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。

更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。

今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

如果要买归类为附件的物品，必须先买该附件所属的主件。

每个主件可以有0个、1个或2个附件。

附件不再有从属于自己的附件。

金明想买的东西很多，肯定会超过妈妈限定的 N 元。

于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。

他还从因特网上查到了每件物品的价格（都是10元的整数倍）。

他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第j件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为j1，j2，…，jk ，则所求的总和为：

v[j1]∗w[j1]+v[j2]∗w[j2]+…+v[jk]∗w[jk] （其中*为乘号）

请你帮助金明设计一个满足要求的购物单。

输入格式 
输入文件的第 1  行，为两个正整数，用一个空格隔开：N,m ，其中 N  表示总钱数，m  为希望购买物品的个数。
从第 2  行到第 m+1  行，第 j  行给出了编号为 j−1  的物品的基本数据，每行有 3  个非负整数 v,p,q ，其中 v 
表示该物品的价格，p  表示该物品的重要度（1~5），q  表示该物品是主件还是附件。

如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件，q  是所属主件的编号。

输出格式
输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<200000）。

数据范围 
N<32000,m<60,v<10000 
输入样例： 
1000 5 
800 2 0 
400 5 1 
300 5 1 
400 3 0
500 2 0
输出样例： 2200 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思路：

这里采用了状态压缩dp，可以用一个数字表示所有的选取状态

//附件有n个就有2的n次方种状态：

可以将每个主件及其附件看作一个物品组，记主件为

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/一键难忘520/article/detail/846636