多重背包
1.题目
2.思路分析
一、状态表示：f[i][j]
1. 集合：从前i个物品中选,且总体积不超过j的所有方案的集合.
2. 属性：最大值
二、状态计算：
1. 思想-----集合的划分
2. 集合划分依据：根据第i个物品有多少个来划分.含0个、含1个···含k个.
状态表示与完全背包朴素代码一样均为：
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
3.Ac代码
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N=1010; static int n,m; static int []v=new int[N]; //体积 static int []w=new int[N]; //价值 static int []s=new int[N]; //数量 static int [][]f=new int[N][N]; //拿了总体积不超过j的情况下的价值最大 public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String str[]=br.readLine().split(" "); n=Integer.parseInt(str[0]); m=Integer.parseInt(str[1]); for (int i = 1; i <=n; i++) { String st[]=br.readLine().split(" "); v[i]=Integer.parseInt(st[0]); w[i]=Integer.parseInt(st[1]); s[i]=Integer.parseInt(st[2]); } for (int i = 1; i <=n; i++) { for (int j = 0; j <=m; j++) { for (int k=0; k<=s[i] &&k *v[i]<=j ;k++) f[i][j]=Math.max(f[i][j] ,f[i-1][j-v[i]*k]+w[i]*k); } } System.out.println(f[n][m]); } }
4.二进制优化方法
如果将背包问题的数据范围扩大呢，那么显然刚刚的做法会超时
取这样一个例子:要求在一堆苹果选出n个苹果。我们传统的思维是一个一个地去选，选够n个苹果就停止。这样选择的次数就是n次
二进制优化思维就是：现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,.....5121,2,4,8,16,.....512分到10个箱子里，那么由于任何一个数字x∈[0,1023]x∈[0,1023] 都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次≤10次 。
比如：
如果要拿10011001次苹果，传统就是要拿10011001次；二进制的思维，就是拿7个箱子就行（分别是装有512、256、128、64、32、8、1512、256、128、64、32、8、1个苹果的这7个箱子）,这样一来，1001次操作就变成7次操作就行了。
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N=12010,M=2010; static int n,m; static int []v=new int[N]; //体积 static int []w=new int[N]; //价值 static int []f=new int[M]; //拿了总体积不超过j的情况下的价值最大 public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String str[]=br.readLine().split(" "); n=Integer.parseInt(str[0]); m=Integer.parseInt(str[1]); int cnt=0; //分组的组别 for (int i = 1; i <=n; i++) { String st[]=br.readLine().split(" "); int a=Integer.parseInt(st[0]); int b=Integer.parseInt(st[1]); int s=Integer.parseInt(st[2]); int k=1; //每组的数量 while (k<= s){ cnt++; v[cnt]= a*k; //整体体积 w[cnt]= b*k; //整体价值 s=s- k; //c要减少 k=k* 2; // 组别里的个数增加 } if(s>0){ cnt++; v[cnt]= a*s; w[cnt]= b*s; } } //这样就把多重背包分成多个 01背包了 n=cnt; for (int i = 1; i <=n; i++) { for (int j = m; j >=v[i]; j--) { f[j]=Math.max(f[j] , f[j-v[i]]+w[i]); } } System.out.println(f[m]); } }
分组背包
1.题目
2.思路分析
给定好多组物品，每组里有若干物品，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
3.Ac代码
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int N=110; static int n,m; static int [][]v=new int[N][N]; //体积 static int [][]w=new int[N][N]; //价值 static int []s=new int[N]; //数量 static int []f=new int[N]; //拿了总体积不超过j的情况下的价值最大 public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String str[]=br.readLine().split(" "); n=Integer.parseInt(str[0]); m=Integer.parseInt(str[1]); for (int i = 1; i <=n; i++) { s[i]=Integer.parseInt(br.readLine()); for (int j = 0; j < s[i]; j++) { String st[]=br.readLine().split(" "); v[i][j]=Integer.parseInt(st[0]); w[i][j]=Integer.parseInt(st[1]); } } for (int i = 1; i <=n; i++) { for(int j=m;j>0;j--){ for(int k=0;k<s[i];k++){ if(j>=v[i][k]) f[j]=Math.max(f[j],f[j-v[i][k]]+w[i][k]); } } } System.out.println(f[m]); } }
感谢你能看完， 如有错误欢迎评论指正，有好的思路可以交流一波，如果对你有帮助的话，点个赞支持下
