背包问题—完全背包问题

74 阅读 0 评论 49 点赞

我是靠谱客的博主大力乐曲，这篇文章主要介绍背包问题—完全背包问题，现在分享给大家，希望可以做个参考。

完全背包问题跟01背包的区别是01背包每个物品只能选一次，总共就这几个，而完全背包问题是每个物品可以无限选，只要装得下。可以看成是有几种物品，每种都无限多个。
如何根据01背包问题的分析成果来分析完全背包呢？其实很简单，
01背包在选第i个物品时，容积够用情况下，只有2种状态可选，放还是不放，找出最大价值的选择。
而完全背包在选第i种物品时，容积够用情况下，可能有2种以上状态可选，放1个，或者2个，3个，或者不放。找出最大价值的选择。
可以利用k = j/weight[i]算出最多可以放几个，然后状态转移方程改为 V[i][j] = max(V[i - 1][j - k*weight[m]] + k * value[i])从0到k遍历一遍求出最大值即可。
方法一
贪心策略预处理
完全背包问题与01背包问题的不同点在于：“每种物品有无限件”，从这一点出发，对于两件物品i和j，如果Ci >= Cj,Wi < Wj，那么以直接去掉物品i，因为显然物品j更加物美价廉。
具体可以采用计数排序实现：设置大小为1到V的V个桶，将每个物品的容量放入对应的桶内。

复制代码

1
2
3
如果同一个桶内有重复的数据，那么仅取较大的。
所有物品都装入桶之后，读取每个桶中的Wi的值，如果有减小的，则直接删去。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 /**
* 预处理方法，去除肯定不可能被添加进背包的物品
* @param c[] 每件物品的容量
* @param w[] 每件物品的价值
* @param v 背包容量
* @return 被选中的物品的c-w对
*/
public HashMap<Integer,Integer> PreProcess(int[] c,int[] w,int v){
if(c.length != w.length){return null;}
else{
//tong[0]弃用，其余位置存放容量为1到v的v个桶
int[] tong = new int[v+1];
//第一个循环，完成桶的填充，在同一个桶中有多个元素时，选取较大的w[i]。
for(int i=0;i<c.length;i++){
tong[c[i]] = tong[c[i]]>w[i]?tong[c[i]]:w[i];
}
//第二个循环，按照桶的容量大小遍历，如果有下面的桶w小于上面的桶的，直接删去（置零）。
int temp = 0;
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
for(int j=1;j<tong.length;j++){
if(tong[j]==0)continue;
else if(tong[j]>temp){
temp = tong[j];
hm.put(j, tong[j]);
}
else tong[j] = 0;
}
//输出key-value对
Set<Integer> set = hm.keySet();
for(Integer g:set){
System.out.println(g+","+hm.get(g));
}
return hm;
}
}

F[ i, v ]代表将前i种物品放入容量为v的背包中所能得到的最大价值。根据第i件物品放入的数量，可以得到如下的状态转移函数：

F[i,v]=max{F[i-1,V−kCi-1]+kWi|0≤kCi≤v}
每个物品可以放的上限为⌊v/Ci⌋⌊v/Ci⌋，为了得到F[ i，v ]需要遍历所有的 k ∈ (1…n) ，找出所有k值下F[ i , v ]的最大值。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public int[][] package_one(int[] c,int[] w,int v){
//预处理，得到处理过的数据c1[]，c2[]。
HashMap<Integer,Integer> hm = PreProcess(c,w);
Set<Integer> set = hm.keySet();
int n = set.size();
int[] c1 = new int[n];
int[] w1 = new int[n];
Object[] c2 = set.toArray();
for(int i=0;i<c2.length;i++){
c1[i] = ((Integer)c2[i]).intValue();
w1[i] = hm.get(c1[i]);
}
//求解所有子问题
int[][] f = new int[n+1][v+1];
for(int i=1;i<n+1;i++){
//循环得到的商品对
for(int j=c1[i-1];j<v+1;j++){ //取出某一对商品的价值
for(int k=0;k<v/c1[i-1];k++){
//循环
终止条件是加入该商品的最大数目
if(j>=k*c1[i-1])
f[i][j] = f[i-1][j-k*c1[i-1]]+k*w1[i-1]>f[i][j]?f[i-1][j-k*c1[i-1]]+k*w1[i-1]:f[i][j];
//判断 前i-1个的 商品价值加上 k*i-1商品的价值大小
}
}
}
return f;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
 public static void main(String[] args){
int c[]={3,4,5,3,6};
int w[]={4,5,6,3,5};
Package02 pack = new Package02();
int[][] f = pack.package_one(c, w,10);
for(int i=0;i<f.length;i++){
for(int j=0;j<f[0].length;j++){
System.out.print(f[i][j]+" ");
}
System.out.println();
}
}

方法二：转化为01背包
01背包问题是最基本的背包问题，我们可以考虑把完全背包问题转化为01背包问题来解。

最简单的想法是，考虑到第i种物品最多选⌊V /Ci⌋件，于是可以把第i种物品转化为⌊V /Ci⌋件费用及价值均不变的物品，然后求解这个01背包问题。这样的做法完全没有改进时间复杂度，但这种方法也指明了将完全背包问题转化为01背包问题的思路：将一种物品拆成多件只能选0件或1件的01背包中的物品。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int[] package_two(int[] c,int[] w,int v){
//预处理，得到处理过的数据c1[]，w1[]。
HashMap<Integer,Integer> hm = PreProcess(c,w);
Set<Integer> set = hm.keySet();
int n = set.size();
int[] c1 = new int[n];
int[] w1 = new int[n];
Object[] c2 = set.toArray();
for(int i=0;i<c2.length;i++){
c1[i] = ((Integer)c2[i]).intValue();
w1[i] = hm.get(c1[i]);
}
// 第一步：生成新的数组，存放所有可能的背包
ArrayList<Integer> arr_1 = new ArrayList<Integer>();
ArrayList<Integer> arr_2 = new ArrayList<Integer>();
for(int i=1;i<n;i++){
for(int j=0;j<=v/c1[i-1];j++){
arr_1.add(c1[i-1]);
arr_2.add(w1[i-1]);
}
}
// 第二步：根据新的数组，利用01背包问题求解
int[] f = new int[v+1];
System.out.println("新的数组长度："+arr_1.size());
for(int i=1;i<=arr_1.size();i++){
for(int j=v;j>=arr_1.get(i-1);j--){
f[j] = max(f[j],f[j-arr_1.get(i-1)]+arr_2.get(i-1));
}
}
return f;
}

方法三
为了节省空间，更高效的转化方法是：把第i种物品拆成费用为Ci2kCi2k、价值为Wi2kWi2k的若干件物品，其中k取遍满足Ci2k≤VCi2k≤V 的非负整数。

这是二进制的思想。因为，不管最优策略选几件第i种物品，其件数写成二进制后，总可以表示成若干个2k2k件物品的和。这样一来就把每种物品拆成O(log ⌊V /Ci⌋)件物品，是一个很大的改进。

相较于方法2.1，利用二进制的思想，在物品的拆分过程中，我们无需开辟大容量的一维数组，仅需存放几个k值。而具体的实现过程可以建立一个ArrayList数组。代码如下：

复制代码

public int[] package_three(int[] c,int[] w,int v){
// 预处理，得到处理过的数据c1[]，w1[]。
HashMap<Integer,Integer> hm = PreProcess(c,w);
Set<Integer> set = hm.keySet();
int n = set.size();
int[] c1 = new int[n];
int[] w1 = new int[n];
Object[] c2 = set.toArray();
for(int i=0;i<c2.length;i++){
c1[i] = ((Integer)c2[i]).intValue();
w1[i] = hm.get(c1[i]);
}
// 第一步：存储所有的k值
ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<n;i++){
int temp = v/c1[i];
int k = -1;
while(temp>0){
arr.add(new ArrayList<Integer>());
k = (int) Math.floor(Math.log(temp)/Math.log(2));
arr.get(i).add(k);
//System.out.println("i=
"+i+"
k=
"+k);
temp -= Math.pow(2, k);
}
}
//第二步：根据k值采用01背包策略
//array 存放每个物品的数量
//第一层循环：代表每一种物品；第二层循环：代表每一种物品的数量；第三层循环，代表每一次添加对应的所有背包容量。
int[] array = new int[n];
for(int i=0;i<n;i++){
for(int g:arr.get(i)){
array[i] += Math.pow(2, g);
}
//System.out.println(array[i]);
}
int[] f = new int[v+1];
for(int i=1;i<=n;i++){
for(int j=0;j<array[i-1];j++){
for(int k=c1[i-1];k<=v;k++){
f[k] = max(f[k-c1[i-1]]+w1[i-1],f[k]);
}
}
}
return f;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 public int[] package_three(int[] c,int[] w,int v){
// 预处理，得到处理过的数据c1[]，w1[]。
HashMap<Integer,Integer> hm = PreProcess(c,w);
Set<Integer> set = hm.keySet();
int n = set.size();
int[] c1 = new int[n];
int[] w1 = new int[n];
Object[] c2 = set.toArray();
for(int i=0;i<c2.length;i++){
c1[i] = ((Integer)c2[i]).intValue();
w1[i] = hm.get(c1[i]);
}
// 第一步：存储所有的k值
ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
for(int i=0;i<n;i++){
int temp = v/c1[i];
int k = -1;
while(temp>0){
arr.add(new ArrayList<Integer>());
k = (int) Math.floor(Math.log(temp)/Math.log(2));
arr.get(i).add(k);
//System.out.println("i=
"+i+"
k=
"+k);
temp -= Math.pow(2, k);
}
}
//第二步：根据k值采用01背包策略
//array 存放每个物品的数量
//第一层循环：代表每一种物品；第二层循环：代表每一种物品的数量；第三层循环，代表每一次添加对应的所有背包容量。
int[] array = new int[n];
for(int i=0;i<n;i++){
for(int g:arr.get(i)){
array[i] += Math.pow(2, g);
}
//System.out.println(array[i]);
}
int[] f = new int[v+1];
for(int i=1;i<=n;i++){
for(int j=0;j<array[i-1];j++){
for(int k=c1[i-1];k<=v;k++){
f[k] = max(f[k-c1[i-1]]+w1[i-1],f[k]);
}
}
}
return f;
}