背包问题knapsack的三种解法（Python 和 C）

最近研究了一下0-1背包问题，题目就不复述了，大家应该都知道的。

确切的说不是三种解法而是四种解法，下面我就一一写来。

0.枚举法

这种是最简单的一种做法，当然也是时间空间复杂度最大的方法，得到的肯定是精确的结果。若有k个背包，则只要变量2^k次方即可，程序如下。

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int ca;
    int mi(int,int);
    int m,c,cao=0;
    int weight[10],value[10];
    int i,k,valuemax[100]={0},wei,val;
    int x[10];
    scanf("%d%d",&m,&c);
    k=0;
    while(m>0||c>0)
    {
        valuemax[cao]=0;
        for(i=0;i<m;i++)
            scanf("%d",&weight[i]);
        for(i=0;i<m;i++)
            scanf("%d",&value[i]);
        for(i=0;i<mi(2,m);i++)
        {
            wei=0;
            val=0;
            ca=i;
            for(k=0;k<m;k++)
            {
                x[k]=i%2;
                i=i/2;

                wei+=x[k]*weight[k];
                val+=x[k]*value[k];
            // k++;
            }
            if(wei<=c&&val>=valuemax[cao])
                valuemax[cao]=val;
            i=ca;
        }
        cao++;
        scanf("%d%d",&m,&c);
    }
    for(i=0;i<cao;i++)
        printf("%d\n",valuemax[i]);

    return 0;
}
int mi(intm,int n)
{
    int sum=1,i;
    for(i=0;i<n;i++)
        sum=sum*m;
    return sum;
}

1.动态规划算法

这个也是一个精确的算法。动态规划，简单说来就是知道一个状态，然后根据状态转移方程得到另外一个状态。根据这两个状态间的转换，递推获得最终解。

那么我们设背包容量为C，然后每个货物的重量为Wj，每个货物的价值为Vj，一共有n个货物。下面我们分情况讨论，

① n个货物的总重量小于背包的总容量。

当然这样我们就解决问题了，就是所有的Vj之和。不要觉得这一部很没用，但凡复杂的问题就可以从简单的问题开始讨论。

② n个货物的总重量大于背包的总容量。

这时候我们可以考虑中间某一个状态，为了区分，我们设在状态i，设此时背包内所剩容量为Ci，当然此时要装的货物重量为Wi，价值为Vi.设此时背包内的可能的最大价值为Value(i, Ci)。

我们继续分解情况：

  Ⅰ Wi > Ci

     很简单的一种情况，此时背包内无法装下Wi的货物，所有就有Value(i, Ci) = Value(i - 1, Ci)

  Ⅱ Wi <= Ci

     此时可以把货物i装进去，课后死我们要不要装呢？这时候我们就可以比较一下把货物转进去会不会导致价值增高啊。也就是我们可以得到公式。Value(i, Ci) = max{Value(i - 1, Ci), Vi + V(i - 1, Ci - Wi)}。

     这样我们就得到了状态方程，根据状态方程就可以轻松的把程序写出来了。

#!/usr/bin/env python
# coding=utf-8
import time
import json


def knapsack(num, cap, wei= [], val = []):
    d =[[i for i in range(cap+ 1)]for j in range(num + 1)]
    wei.insert(0,0)
    val.insert(0,0)
    for iin range(num + 1):
        d[i][0]= 0
    for iin range(cap + 1):
        try:
            d[0][i]= 0
        except:
            pass
#            print i
    for iin range(1, num + 1):
        for j in range(1, cap+ 1):
            d[i][j] = d[i - 1][j]
            if wei[i] <= j:
                temp = val[i] + d[i -1][j - wei[i]]
                iftemp > d[i - 1][j]:
                    d[i][j]= temp
    return d[num][cap]

start = time.clock()
num = 100
cap = 10000
f = open('weight.txt','r')
weight = json.load(f)
f.close()
f = open('value.txt','r')
value = json.load(f)
f.close()

print knapsack(num, cap, weight, value)
timeused = time.clock() - start
print '用时：', timeused

2.贪心(Greedy)算法

所谓贪心，就是能装多少就装多少，显然他不是精确算法。我们可以在进行贪心算法之前对程序进行排个序，把价值与重量之比大的货物放在前面，其实是没有这个必要的，因为当数据很大的时候，是否排序对最终结果没有多少影响，不过对于数据很少的情况下还是有蛮大影响的。下面就是代码咯

#!/usr/bin/env python
# coding=utf-8
import time
import json

def greedydp(num, cap, weight= [], value = []):
    p =[0] * num
    q =[0] * num
    for i in range(num):
        p[i] =weight[i] / value[i]
        q[i] =i
    for iin range(num):
        j =i + 1
        while j > i and j < num:
            if p[i] > p[j]:
                t = q[i]
                q[i] = j
                q[j] = t
                t = p[i]
                p[i] = p[j]
                p [j] = t
            j +=1
    sumwei =sum = 0
    for iin range(num):
        for j in range(num):
            if p[j] == i:
                ifweight[j] + sumwei <= cap:
                    sum+= value[j]
                    sumwei+= weight[j]
    return sum

start = time.clock()
num = 100
cap = 10000
f = open('weight.txt','r')
weight = json.load(f)
f.close()
f = open('value.txt','r')
value = json.load(f)
f.close()

print greedydp(num, cap, weight, value)
timeused = time.clock() - start
print '用时：', timeused

3.基于Greedy的Rollout算法

这个算法呢，其实也是很简单的，不过在搜索相关资料的时候，却在国内很少看到相关算法，应该是国内不称作Rollout算法，而是称为启发式算法。

从启发式算法这个名字，我们可以知道这个算法是以某一算法启发而来的。也就是以某一算法作为基础，然后对其进行一些变化或者什么的使得这个算法更加的精确。当然，伴随着结果的精确肯定要付出一些代价的，世界上没有免费的午餐的，这个代价就是增加了时间复杂度，为什么呢？因为他是在贪心算法的基础上增加了一次循环。

我们这个选择货物按照编号从1到n选择，然后当选择到第t个的时候，我们考虑要不要把这个货物装进背包，如果我们看到他的重量小于此时背包的容量就装进去的话就变成了贪心算法，可是如果我们把他分成两种情况进行考虑的话，就是装与不装，然后分别进行贪心算法，然后在选择较大的情况，就ok了。

#!/usr/bin/env python
# coding=utf-8

import random
import json
import time

def sort2(num, weight = [], value = []):
    x =[[] for i in range(num)]
    #print x
    for iin range(num):
        x[i].append(weight[i])
        x[i].append(value[i])
        x[i].append(float(value[i])/weight[i])
    for iin range(num):
        for j in range(i, num):
            if x[i][2] < x[j][2]:
                t = x[i]
                x[i] = x[j]
                x[j] = t
    for iin range(num):
        weight[i] = x[i][0]
        value[i] = x[i][1]

    return weight, value

def greedy(num, cap, weight=[], value=[]):
    sumwei =sum = 0
    for iin range(num):
        if weight[i] + sumwei <= cap:
            sum+= value[i]
            sumwei += weight[i]
    return sum


def rollout(num, cap, weight=[], value=[]):
    leftweight = [i for i in weight]
    leftvalue =[i for i in value]
    notchoose =[i for i in range(num)]
    choose =[]
    choosenum =1
    choosedig =-1
    choosevalue = 0
    summax =0
    valueatlast = 0
    i =0
    for tin range(num):

        flag =-1
        for i in notchoose:

            flag += 1
            if weight[i] <= cap:
                cap -= weight[i]
                choose.append(i)
                leftvalue.pop(flag)
                leftweight.pop(flag)

                tempsum= choosevalue + value[i] + greedy(num - len(choose), cap, leftweight, leftvalue)

                leftweight.insert(flag, weight[i])
                leftvalue.insert(flag, value[i])
                cap += weight[i]
                choose.pop()
                iftempsum >= summax:
                    summax= tempsum
                    choosedig= i
        if choosedig >= 0:
#                    print choosedig
                    choose.append(choosedig)
                    notchoose.remove(choosedig)
                    leftvalue.remove(value[choosedig])
                    leftweight.remove(weight[choosedig])
                    cap-= weight[choosedig]
                    choosevalue+= value[choosedig]
                    choosedig= -1

    return summax

start = time.clock()
num = 100
cap = 10000
f = open('weight.txt','r')
weight = json.load(f)
f.close()
f = open('value.txt','r')
value = json.load(f)
f.close()

print rollout(num, cap, weight, value)
timeused = time.clock() - start
print '用时：', timeused

总结：我们同过生成100组随机数据对三种算法进行了测试，结果如下：

测试数据为100个货物，背包容量为10000，采用随机数生成1----500的数作为重量，用程序运行结束时的时间与开始时的时间之差作为计时标准。 则结果如下：

算法名称 |结果 |        耗时              |结果2 |耗时2

Greedy |9110 |0.00157397626884 |10221 |0.0016819459503

Rollout |14463 |0.0354518243797|13457|0.0590536683212

动态规划 |14738 |0.492143871448 |14737|0.48608771654

生成随机数的算法还是很简单的。

详细代码级结果可参见我的Github: https://github.com/zhangzhishan/knapsack