【算法学习笔记】贪心算法背包问题

发表于 | 分类于 |

贪心算法是我们在《计算机算法设计与分析》这门课中学习的几种重要的算法之一，顾名思义，贪心算法总是做出在当前看来最好的选择。也就是该算法并不从整体最优考虑，它所作出的选择只是在某种意义上的从局部的最优选择，寻找到解决问题的次优解的方法。虽然我们希望贪心算法得到的最终结果也是整体最优的，但是在某些情况下，该算法得到的只是问题的最优解的近似。

贪心算法思路

————问题通常以自顶向下的方式进行，以迭代的方式做出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。当达到算法中的某一步（不可简化的子问题）不能再继续前进时，算法停止。
该算法存在的短板：

  1. 不能保证求得的最后解是最佳的；
  2. 不能用来求最大或最小解问题；
  3. 只能求满足某些约束条件的可行解的范围。

实现该算法的过程：
Begin 从问题的某一初始解出发；
while 能朝给定总目标前进一步
do 求出可行解的一个解元素；
end 由所有解元素组合成问题的一个可行解

背包问题描述

  1. 0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包（1）或不装入背包（0）。不能将物品i装入背包多次，也不能只装入部分的物品i。
  2. 背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。背包问题可以定义如下：给出n个大小为w1,w2,…,wn,值为v1,v2,…,vn的项目，并设背包容量为C，要找到非负实数x1,x2,…,xn, 使和在约束下最大。

贪心算法解决背包问题有几种策略：

(i) 一种贪婪准则为：

从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], v =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。

(ii) 另一种方案是重量贪婪准则是：

从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], v=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。

(iii) 还有一种贪婪准则，就是我们教材上提到的：

认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], v=[40,25,25], c=30 时的最优解。虽然按pi /wi 非递减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。而且这是解决普通背包问题的最优解，因为在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。

Code

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<queue>
#include<climits>
#include<cstring>

using namespace std;

float c = 10;    //背包容量
float w[] = {0,10,2,6,5,4};    //物品质量
float v[] = {0,6,3,5,4,6};    //物品价值
const int n = sizeof(w)/sizeof(w[0]) - 1 ;    //物品品种数
float x[n+1];    //背包中某种物品的质量（结果）

void Sort(int n,float v[],float w[])    //对物品的单位价值排序
{
    for(int i = 1;i <= n;i++)
    {
        for(int j = i;j <= n;j++)
        {
            if(v[i]/w[i] < v[j]/w[j])
            {
                float tempv = v[i];
                v[i] = v[j];
                v[j]=tempv;

                float tempw = w[i];
                w[i] = w[j];
                w[j] = tempw;
            }
        }

    }
}

void printSort(int n,float v[],float w[])    //输出排序后结果
{
     for(int i = 1;i <= n;i++)
     {
        cout<<"v:"<<" "<<v[i]<<"    ";
        cout<<"w:"<<" "<<w[i]<<endl;
     }
}

void Knapsack(int n,float c,float v[],float w[],float x[])    //贪心选择
{
    Sort(n,v,w);
    int i;
    for(i = 1;i <= n;i++)
        x[i] = 0;
    //float c = M;
    for(i = 1;i <= n;i++)
    {
         if(w[i] > c)
             break;
         x[i] = 1;
         c-=w[i];
    }
    if(i <= n)
        x[i]= c/w[i];
}

int main()
{
    Knapsack(n,c,v,w,x);
    printSort(n,v,w);
    //输出结果
    cout << "The best answer is:\n";
    for(int j =1; j <= 5; j++)
    {
         cout << v[j] << " ";
    }
    cout << endl;
    for(int i = 1; i <= 5; i++)
        cout << x[i] * w[i] << " ";
    //system("pause");
    return 0;
}