第六重关：分组背包

本文主要是介绍第六重关：分组背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

已知如下条件：

    N个物品

    容量为V的背包

    vi：第i个物品所占用的容量空间

    valuei：第i个物品所获得的价值数值

    这些背包被分成了p个组，并且每个组里面的物品最多选择一件或者不选

求解：

    该背包可以装下的最大价值是多少？

解题思路：

如果不看组内的细节的话，其实这就是一个01背包，所以第一层FOR循环，显然就是遍历组别。对于一个分组，有两种结果，选取组内最好的和不选。那么在第二重FOR的时候表示，是否选取这个组别，如果选取该组，那么我就要选取该组中价值最高。如果不选，那就不去选择即可。

for (int i = 1; i <= P; i++)
{    for (int j = V; j >= 0; j--){for (int k: Park[i]){if (j > v[k]){dp[j] = MAX(dp[j], dp[j - v[k]] + w[k]);}}}
}

题目：HDU 4341（这题目要是读不懂，对不起自己童年）

注意点：1）计算斜率的时候要注意y是不能等于0的，但是x是可以等于0的；2）如果斜率一样的话要按照y的大小进行排序，原因是钩子是从上面往下放出去的。它一定要先抓浅层的金矿，然后才能去抓深层的金矿。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int max_N = 201;
const int max_T = 40001;
const double eps = 0.000001;
struct NODE
{int x, y;int t, v;double mult;
}node[max_N];bool cmp(NODE a, NODE b)
{if (a.mult != b.mult) return a.mult < b.mult;else if (a.y != b.y) return a.y < b.y;
}double ABS(const double x)
{if (x > 0) return x;else return -x;
}int MAX(const int x, const int y)
{if (x > y) return x;else return y;
}int main()
{int N, T;int Case = 0;while (cin>> N>> T){int dp[max_T], tmp[max_T];memset(dp, 0, sizeof(dp));for (int i = 1; i <= N; i++){cin>> node[i].x>> node[i].y>> node[i].t>> node[i].v;node[i].mult = node[i].x*1.0 / node[i].y;}sort(node+1, node+N+1, cmp);for (int i = 2; i <= N; i++){if (node[i].mult == node[i-1].mult){node[i].t += node[i-1].t;node[i].v += node[i-1].v;}}for (int i = 1; i <= N; ){int k;for (int j = T; j >= 0; j--){for (k = i; k <= N && ABS(node[k].mult - node[i].mult) < eps; k++){if (node[k].t <= j){dp[j] = MAX(dp[j], dp[j-node[k].t] + node[k].v);}}}i = k;}cout<< "Case "<< ++Case<< ": ";cout<< dp[T]<< endl;}return 0;
} 

 

 

这篇关于第六重关：分组背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---