此题实际上就是一个分组背包问题
通过理解题意之后,按照题意进行分组。
多少个主物品就代表有多少组。
多少个附件,就划分为了一个组中多少中物品
如2个附件,a1,a2,一个主物品,c
则可以组成
c.
c,a1.
c,a2.
c,a1,a2.
其每个组中的划分只能用其中的一个。
所以求出对应的组的每个划分块需要多少钱(相当于体积),钱 * 重要程度(相当于价值)
此题最重要的一个地方就是使用二进制优化:
一共有n个物品,求n个物品每一个一组,每两个一组,每三个一组....一直到每n个一组可以使用二进制来进行表示,枚举的一个技巧。
for(int k = 0 ; k < 1 << n ; k++) // 1 << n结果为: 10000...0。 一个“1”,n个“0”。
{
for(int u = 0 ; u < n ; u++) //判断n个位即可
{
if(k >> u & 1) //就可以判断对应的位是否为1,代表某个物品被选中。 u 为 0 时,代表第一个物品被选中。u为1,代表第二个物品被选中。
{
}
}
}
代码实现:
# include <iostream>
# include <vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 32010 , M = 70 , V = 10010;
int v,w,book;
PII master[M]; //主物品
vector<PII> child[M]; //附件
vector<PII> group[M]; //对应的分组背包,其中存了体积(first),和价值(second)。
// int f[M][N]; //二维
int f[N]; //一维
int n,m;
int main()
{
scanf("%d %d",&n,&m);
for(int i = 1 ; i <= m ; i++)
{
scanf("%d %d %d",&v,&w,&book);
if(!book)
{
master[i] = {v,w * v};
}
else
{
child[book].push_back({v,v * w});
}
}
int cnt = 1; //分组背包数
for(int i = 1 ; i <= m ; i++)
{
if(master[i].first) //为主
{
/* // 下面的代码可以使用二进制进行优化
group[cnt].push_back({master[i].first,master[i].second});
if(child[i].size() == 1)
{
group[cnt].push_back({master[i].first + child[i][0].first,master[i].second + child[i][0].second});
}
else if(child[i].size() == 2)
{
group[cnt].push_back({master[i].first + child[i][0].first , master[i].second + child[i][0].second});
group[cnt].push_back({master[i].first + child[i][1].first , master[i].second + child[i][1].second});
group[cnt].push_back({master[i].first + child[i][0].first + child[i][1].first , master[i].second + child[i][0].second + child[i][1].second});
}
*/
//使用二进制优化
for(int k = 0 ; k < 1 << child[i].size() ; k++) //1 << 2 == 100(2进制), 其中包含了00,01,10,11这三种情况,于是可以用这四种情况判断用了哪些物品
{
int temp1 = master[i].first , temp2 = master[i].second;
for(int u = 0 ; u < child[i].size() ; u++)
{
if(k >> u & 1)
{
temp1 += child[i][u].first;
temp2 += child[i][u].second;
}
}
group[cnt].push_back({temp1,temp2});
}
cnt++;
}
}
cnt--; //共cnt组背包。每组背包group[i].size()个物品
/* //二维:
for(int i = 1 ; i <= cnt ; i++)
{
for(int j = 0 ; j <= n ; j++)
{
f[i][j] = f[i - 1][j]; //不要这个物品
for(int k = 0 ; k < group[i].size() ; k++) //因为push_back的下标从0开始,实际上k == 0是第一个物品了已经
{
if(j >= group[i][k].first)
{
f[i][j] = max(f[i][j],f[i - 1][j - group[i][k].first] + group[i][k].second);
}
}
}
}
printf("%d\n",f[cnt][n]);*/
for(int i = 1 ; i <= cnt ; i++)
{
for(int j = n ; j >=0 ; j--)
{
for(int k = 0 ; k < group[i].size() ; k++)
{
if(j >= group[i][k].first)
{
f[j] = max(f[j],f[j - group[i][k].first] + group[i][k].second);
}
}
}
}
printf("%d\n",f[n]);
return 0;
}
%%%本题最好的题解
写的真好
打印一下分组背包中每一组的组内物品,会更加清楚。
nb
写的很详细 清晰明了