背包问题之分组背包

目录

1、基本了解

2、例题

3、例题分析

4、减少空间复杂度

参考文献

1、基本了解

问题描述

有N件物品和一个容量为V的背包。第i件物品的费用是w[i]，价值是c[i]。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

算法

这个问题变成了每组物品有若干种策略:是选择本组的某一件，还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值，则有f[k][v]=max{f[k-1][v],f[k-1][v-w[i]]+c[i]},物品i属于第k组。 使用一维数组的伪代码如下:

for 所有的组k for v=V..0 for所有的i属于组k f[v]=max{f[v],f[v-w[i]l +c[i]}

动图说明：

题目要求：

生成的数组：

dp状态转移数组：

上表有两个值错误，更正后应该是：dp[2][2] =1,dp[2][3] = 3

2、例题

【问题描述】

一个旅行者有一个最多能用V公斤的背包，现在有n件物品，它们的重量分别是W1， W2，...Wn，它们的价值分别为C1,C2....Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

【输入格式】

第一行：三个整数，V(背包容量，V<=200)，N(物品数量，N<=30)和T(最大组号，T<=10);

第2..N+1行：每行三个整数Wi,Ci,P，表示每个物品的重量，价值，所属组号。

【输出格式】仅一行，一个数，表示最大总价值。

【样例输入】

10 6 32 1 13 3 14 8 26 9 22 8 33 9 3

【样例输出】

20

3、例题分析

每组物品只选一件，所以遍历dp数组是从后往前遍历共有T个小组，所以大循环T次背包的体积是从V ~ 0 之间，每个小组的每个物品需要考虑插入或者不插入（插入后的价值是否更高，因为有些物品体积很大，但是价值不高），能插入或者不能插入（剩余的体积是否允许插入当前这个物品）两个问题。如果剩余空间能够插入，那么dp[i][j] = max(dp[i-1][j-w[temp]]+c[temp)

代码：

import java.util.Scanner;import javax.xml.crypto.dsig.spec.DigestMethodParameterSpec;public class _分组背包Sample {//最大的物品数量static int MAX_NUM = 35;//最大的组号static int MAX_GROUP = 15;//最大的背包容量static int MAX_VOLUME = 205;//存储物品的重量static int w[] = new int[MAX_NUM];//存储物品的价值static int c[] = new int[MAX_NUM];//存储每个小组有哪些物品static int a[][] = new int[MAX_GROUP][MAX_VOLUME];//动态转移数组static int dp[][] = new int[MAX_NUM][MAX_VOLUME];public static void main(String[] args) {//V :背包容量//N : 物品数量//T :最大组号int V,N,T;System.out.println("Please input data:");Scanner input = new Scanner(System.in);V = input.nextInt();N = input.nextInt();T = input.nextInt();//p:所属组号int p;//将输入的数据输入w、v、a数组for(int i=1;i<=N;i++) {w[i] = input.nextInt();c[i] = input.nextInt();p = input.nextInt();//将所属a[p]的物品的序号添加到数组后面a[p][++a[p][0]] = i;}//动态规划for(int i=1;i<=T;i++) {//组号for(int j=V;j>=0;j--) {//背包的体积for(int k=1;k<=a[i][0];k++) {//组号i内的物品号int temp = a[i][k];if(j>=w[temp]) {if(dp[i][j] < (dp[i-1][j-w[temp]]+c[temp]))dp[i][j] = dp[i-1][j-w[temp]]+c[temp];}}}}System.out.println(dp[T][V]);}}

4、减少空间复杂度

可以使用以为数组来存储dp[i][j]的值，两组之间的选择互不干扰。

主要代码：

for(int i=1;i<=T;i++) {//组号for(int j=V;j>=0;j--) {//背包的体积for(int k=1;k<=a[i][0];k++) {//组号i内的物品号int temp = a[i][k];if(j>=w[temp]) {if(dp[j] < (dp[j-w[temp]]+c[temp]))dp[j] = dp[j-w[temp]]+c[temp];}}}}

动图展示：

参考文献

[1] 分组背包

如果觉得《背包问题之分组背包》对你有帮助，请点赞、收藏，并留下你的观点哦！