目录
1、预处理首先把每个物品按照组号g[i]从小到大排序,假设总共有t组,则将g[i]按顺序离散到[1,t]的正整数
2、状态设计状态(k,j)表示前k组物品恰好放入容量为j的背包(k属于[0,t],j属于[0,m])
4、时间复杂度分析对于n个物品放入一个容量为m的背包,状态数为O(nm),每次状态转移的消耗为O(1),所以整个状态转移的过程时间复杂度是O(nm)
Question:
有n(n <= 1000)个物品和一个容量为m(m <= 1000)的背包。这些物品被分成若干组,第i个物品属于g[i]组,容量是c[i],价值是w[i],现在需要选择一些物品放入背包,并且每组最多放一个物品,总容量不能超过背包容量,求能够达到的物品的最大总价值。
1、预处理
首先把每个物品按照组号g[i]从小到大排序,假设总共有t组,则将g[i]按顺序离散到[1,t]的正整数
这样做的目的是为了将g[i]作为下标映射到状态数组中
2、状态设计
状态(k,j)表示前k组物品恰好放入容量为j的背包(k属于[0,t],j属于[0,m])
令dp[k][j]表示状态(k,j)下该背包得到的最大价值,即前k组物品(每组物品至多选一件)恰好放入容量为j的背包所得到的最大总价值;因为每个物品有只有两种情况
3、状态转移方程
1) 不放 : 如果“第i个物品(属于第k组)不放入容量为j的背包”,那么问题转化成求”前k-1组物品放入容量为j的背包”的问题
由于不放,所以最大价值就等于“前k-1组物品放入容量为j的背包”的最大价值,对应状态转移方程中的dp[k-1][i]
2) 放 : 如果“第i个物品(属于第k组)放入容量为j的背包”,那么问题转化成求“前k-1组物品放入容量为j-c[i]的背包”的问题
那么此时最大价值就等于“前k-1组物品放入容量为j-c[i]的背包”的最大价值加上放入第i个物品的价值,即dp[k-1][j-c[i]]+w[i]
因为前k-1组物品中一定不存在第k组中的物品,所以能够满足“最多放一个”这个条件
4、时间复杂度分析
对于n个物品放入一个容量为m的背包,状态数为O(nm),每次状态转移的消耗为O(1),所以整个状态转移的过程时间复杂度是O(nm)
注意在分组背包求解的时候,要保证相同组的在一起求,而一开始的预处理和离散化正式为了保证这一点,这样,每个物品的组号为g[i]=1,2,3,4 ... ,t,并且我们可以把状态转移方程进一步表示成和k无关的,如下
代码示例 :
# python 代码示例
def group_knap_sack(n, m, items) :
items.sort(key = lambda x : x[0])
groups = []
current_group = -1
for g, c, w in items :
if g != current_group :
groups.append([])
current_group = g
groups[-1].append((c, w))
t = len(groups)
dp = [ [-float('inf')] * (m + 1) for _ in range(t + 1)]
dp[0][0] = 0
for k in range(1, t + 1) :
for j in range(1, m + 1) :
dp[k][j] = dp[k - 1][j]
for c, w in groups[k - 1] :
if j >= c :
dp[k][j] = max(dp[k][j], dp[k - 1][j - c] + w)
max_value = max(dp[t])
return max_value
n = 7
m = 10
items = [
(1, 2, 3), # 组号1, 容量2, 价值3
(1, 3, 4), # 组号1, 容量3, 价值4
(2, 4, 5), # 组号2, 容量4, 价值5
(3, 1, 2), # 组号3, 容量1, 价值2
(3, 2, 2), # 组号3, 容量2, 价值2
(4, 5, 10), # 组号4, 容量5, 价值10
(5, 3, 6) # 组号5, 容量3, 价值6
]
print(group_knapsack(n, m, items)) # 输出最大价值// c++ 代码示例
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std ;
struct Item
{
int group ;
int cost ;
int value ;
};
bool compare(const Item &a, const Item &b)
{
return a.group < b.group ;
}
int groupKnapSack(int n, int m, vector<Item> &items)
{
sort(items.begin(), items.end(), compare) ;
vector<vector<pair<int, int>>> groups ;
int currentGroup = - 1 ;
for (const auto &item : items)
{
if (item.group != currentGroup)
{
groups.emplace_back() ;
currentGroup = item.group ;
}
group.back().emplace_back(item.cost, item.value) ;
}
int t = groups.size() ;
vector<vector<int>> dp(t + 1, vector<int>(m + 1,INT_MIN)) ;
for (int k = 1 ; k <= t ; k++)
{
for (int j = 0 ; j <= m ; j++)
{
dp[k][j] = dp[k - 1][j] ;
for (const auto &[c, w] : groups[k - 1])
{
if (j >= c && dp[k - 1][j - c] ！= INT_MIN)
{
dp[k][j] = max(dp[k][j], dp[k - 1][j - c] + w) ;
}
}
}
}
int maxValue = 0 ;
for (int j = 0 ; j <= m ; j++)
{
maxValue = max(maxValue, dp[t][j]) ;
}
return maxValue ;
}
int main()
{
int n = 7 ;
int m = 10 ;
vector<Item> items = {
{1, 2, 3}, // 组号1, 容量2, 价值3
{1, 3, 4}, // 组号1, 容量3, 价值4
{2, 4, 5}, // 组号2, 容量4, 价值5
{3, 1, 2}, // 组号3, 容量1, 价值2
{3, 2, 2}, // 组号3, 容量2, 价值2
{4, 5, 10}, // 组号4, 容量5, 价值10
{5, 3, 6} // 组号5, 容量3, 价值6
}
cout << "最大价值: " << groupKnapSack(n, m, items) << endl ;
return 0 ;
}空间优化代码
时间复杂度已经无法优化,那么空间复杂度是否可以像0/1背包那样进行降维呢?
1、空间复杂度优化
考虑前k组的状态依赖前k-1组的子结果,所以第一层循环应该是枚举“组”;
然后我们尝试将“组”那一维的状态去掉,得到状态转移方程如下:
考虑这里的物品最多只能取1个,类似0/1背包,所以容量枚举需要采用逆序
这时候,我们把物品枚举放外层,容量枚举放内层,会发现变成了第k组内的0/1背包问题,而这不是我们想要的,我们要求一个组内只能最多取一个物品。所以调整顺序:容量枚举放外层,物品枚举放内层。于是,得到了一个降维后的算法,三层循环:枚举组1->t、枚举容量m->0、枚举组内物品i
# python 代码示例
def group_knap_sack_comp(n, m, items) :
items.sort(key = lambda x : x[0])
groups = []
current_group = -1
for g, c, w in items :
if g != current_group :
groups.append([])
current_group = g
groups[-1].append((c, w))
t = len(groups)
dp = [-float('inf')] * (m + 1)
dp[0] = 0
for k in range(t) :
new_dp = dp[:]
for c, w in groups[k] :
for j in range(m, c - 1, -1) :
new_dp[j] = max(dp[j], dp[j -c] + w)
dp = new_dp
max_value = max(dp)
return max_value
n = 7
m = 10
items = [
(1, 2, 3), # 组号1, 容量2, 价值3
(1, 3, 4), # 组号1, 容量3, 价值4
(2, 4, 5), # 组号2, 容量4, 价值5
(3, 1, 2), # 组号3, 容量1, 价值2
(3, 2, 2), # 组号3, 容量2, 价值2
(4, 5, 10), # 组号4, 容量5, 价值10
(5, 3, 6) # 组号5, 容量3, 价值6
]
print(group_knapsack(n, m, items)) # 输出最大价值
// c++ 代码示例
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
using namespace std ;
struct Item
{
int group ;
int cost ;
int value ;
};
bool compare(const Item &a, const Item &b)
{
return a.group < b.group ;
}
int groupKnapSack(int n, int m, vector<Item> &items)
{
sort(items.begin(), items.end(), compare) ;
vector<vector<pair<int, int>>> groups ;
int currentGroup = -1 ;
for (const auto &item : items)
{
if (item.group != currentGroup)
{
groups.emplace_back() ;
currentGroup = item.group ;
}
groups.back().emplace_back(item.cost, item.value) ;
}
int t = groups.size() ;
vector<int> dp(m + 1, INT_MIN) ;
dp[0] = 0 ;
for (int i = 0 ; i < t ; t++)
{
vector<int> new_dp = dp ;
for (const auto &[c, w] : groups[k])
{
for (int j = m ; j >= c ; j--)
{
if (dp[j - c] != INT_MIN)
{
new_dp[j] = max(new_dp[j], dp[j - c] + w) ;
}
}
}
dp = new_dp ;
}
int maxValue = 0 ;
for (int j = 0 ; j <= m ; j++)
{
maxValue = max(maxValue, dp[j]) ;
}
return maxValue ;
}
int main()
{
int n = 7 ;
int m = 10 ;
vector<Item> items = {
{1, 2, 3}, // 组号1, 容量2, 价值3
{1, 3, 4}, // 组号1, 容量3, 价值4
{2, 4, 5}, // 组号2, 容量4, 价值5
{3, 1, 2}, // 组号3, 容量1, 价值2
{3, 2, 2}, // 组号3, 容量2, 价值2
{4, 5, 10}, // 组号4, 容量5, 价值10
{5, 3, 6} // 组号5, 容量3, 价值6
}
cout << "最大价值: " << groupKnapSack(n, m, items) << endl ;
return 0 ;
}例题练手
https://acm.hdu.edu.cn/showproblem.php?pid=1712
#include <iostream>
#include <cstring>
#include <algorithm> // for std::max
using namespace std;
int w[105][105];
int f[105] = {0};
int main() {
int n, m;
while (cin >> n >> m) {
if (!n && !m) break;
// 将所有的元素置为0
memset(f, 0, sizeof(f));
// w[i][j]表示在i课程上花j天学习所获得的价值
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 = m; j >= 0; j--)
for (int k = 1; k <= m; k++)
if (j >= k) // 剩余的背包容量j还够学习k天的话
f[j] = max(f[j], f[j - k] + w[i][k]);
cout << f[m] << '\n';
}
return 0;
}
