背包问题（三）

一、二维费用的背包问题

题目链接

#include<iostream>
#include<algorithm>
using namespace std;
const int M = 110;
int n,m,kg;
int f[M][M];int main()
{cin >> n >> m >> kg;for(int i = 0;i < n;i ++){int v,M,w;cin >> v >> M >> w;for(int j = m;j >= v;j --)for(int k = kg;k >= M;k --){f[j][k] = max(f[j][k], f[j - v][k - M] + w);}}cout << f[m][kg];return 0;
}

二、潜水员

题目链接

题解来源：小呆呆 ,

这个题相较于二维费用的背包问题，稍稍有一点改变，二维费用的背包模板是体积不超过V，重量不超过M，但是这个题是体积至少为V，重量至少为M。

对比两题的思路，二维费用的背包问题，求的是不能超过体积V，重量M的情况下，能拿到价值的最大值。而本题是至少需要体积V，重量M的情况下，能拿到价值的最小值。就拿体积来说，至少需要多少体积，也就是说有体积比需要的体积大的物品还是能用得到，例如f[3][5]，至少需要3个体积，5个重量，求能拿到价值的最小值，现在只有一个物品，体积是4，重量是4，价值w，它说至少需要3个体积，那么体积是4还是可以用到，只是多了1个体积没用占着而已，不影响其价值。因此若用了这个物品，则变成了求f[0][1] + w，表示体积已经不再需求了，只需要0个体积即可

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;int n,m,k;
const int M = 25, N = 82;
int f[M][N];
const int INF = 0x3f3f3f3f;int main()
{cin >> m >> n;cin >> k;memset(f, 0x3f, sizeof f);f[0][0] = 0;for(int i = 1;i <= k;i ++){int a,b,c;cin >> a >> b >> c;for(int j = m;j >= 0;j --)for(int x = n;x >= 0;x --){f[j][x] = min(f[j][x], f[max(0,j - a)][max(0, x - b)] + c);}}cout << f[m][n];return 0;
}

三、机器分配

题目链接

#include<iostream>
#include<algorithm>
using namespace std;int n,m;
const int N = 12, M = 18;
int f[N][M];
int ne[M];
int w[N][M];
int way[M];int main()
{cin >> n >> m;for(int i = 1;i <= n;i ++)for(int j = 1;j <= m;j ++)cin >> w[i][j];for(int i = 1;i <= n;i ++){for(int j = 0;j <= m;j ++){for(int k = m;k >= j;k --)f[i][k] = max(f[i][k], f[i - 1][k - j] + w[i][j]);}}cout << f[n][m] << endl;int j = m;for(int i = n;i >= 1;i --)for(int k = 0;k <= m;k ++)if(f[i][j] == f[i - 1][j - k] + w[i][k]){way[i] = k;j -= k;break;}for(int i = 1;i <= n;i ++) cout << i << " " << way[i] << endl;return 0;
}

四、开心的金明

这个题很容易，就是一个01背包问题

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 30100;
int n,m;
int f[N];int main()
{cin >> n >> m;for(int i = 1;i <= m;i ++){int v,w;cin >> v >> w;for(int j = n;j >= v;j --)f[j] = max(f[j], f[j - v] + v * w);}cout << f[n];return 0;
}

五、有依赖的背包问题

题目链接

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int head[N],e[N],ne[N],idx;
int n,m;
int v[N],w[N],p;
bool st[N];
int f[N][N];void add(int a,int b)
{e[idx] = b, ne[idx] = head[a], head[a] = idx ++;
}void dfs(int u)
{for(int i = head[u]; ~i;i = ne[i]){int son = e[i];dfs(e[i]);for(int j = m - v[u];j >= 0;j --){for(int k = 0;k <= j;k ++)f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);}}for(int i = m;i >= v[u];i --) f[u][i] = f[u][i - v[u]] + w[u];for(int i = 0;i < v[u];i ++) f[u][i] = 0;
}int main()
{cin >> n >> m;memset(head, -1,sizeof head);int root;for(int i = 1;i <= n;i ++){cin >> v[i] >> w[i] >> p;if(p == -1) {   root = i;continue;}add(p, i);st[i] = true;}dfs(root);cout << f[root][m];return 0;
}