背包问题

    背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领 域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkel和Hellman提出的。

问题描述：
   假定有n个物体和一个背包，物体i 有质量wi，价值为pi，而背包的载荷能力为M。若将物体i的一部分xi（1<=i& lt;=n,0<=xi<=1)装入背包中，则有价值pi*xi。在约束条件（w1*x1+w2*x2+…………+wn*xn)<=M下使目标(p1*x1+p2*x2+……+pn*xn)达到极大，此处0<=xi<=1,pi>0,1<=i<=n.这个 问题称为背包问题（Knapsack problem）。

问题分析：
   要想得到最优解，就要在效益增长和背包容量消耗两者之间寻找平衡。也就是说，总应该把那些单位效益最高的物体先放入背包。

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

#define MAXSIZE 100 //假设物体总数

#define M 20 //背包的载荷能力


//算法核心，贪心算法

void GREEDY(float w[], float x[], int sortResult[], int n)
{
    float     cu = M;
    int     i = 0;
    int    temp = 0;

    for (i = 0; i < n; i++)//准备输出结果

    {
        x[i] = 0;
    }

    for (i = 0; i < n; i++)
    {
        temp = sortResult[i];//得到取物体的顺序

        if (w[temp] > cu)
        {
            break;
        }

        x[temp] = 1;//若合适则取出

        cu -= w[temp];//将容量相应的改变

    }

    if (i <= n)//使背包充满

    {
        x[temp] = cu / w[temp];
    }

}

//得到本算法的所有输入信息

void getData(float p[], float w[], int *n)
{
        int i = 0;

        printf("please input the total count of object: ");
        scanf("%d", n);

        printf("Please input array of p :\n");
        for (i = 0; i < (*n); i++)
        {
            scanf("%f", &p[i]);
        }

        printf("Now please input array of w :\n");
        for (i = 0; i < (*n); i++)
        {
            scanf("%f", &w[i]);
        }

}

void output(float x[], int n)
{
    int i;

    printf("---------------------------------------------\n");
    for (i = 0; i < n; i++)
    {
        printf("x[%d]\t\t", i);
    }

    printf("\n");
    for (i = 0; i < n; i++)
    {
        printf("%-8.5f\t", x[i]);
    }
    printf("\n");
    printf("----------------------------------------------\n");

}

void SortIndex(float tempArray[], int sortResult[], int n)
{
    int    i, j, index, max;
    max = tempArray[0];
    index = 0;
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            if(max < tempArray[j])
            {
                max = tempArray[j];
                index = j;
            }
        }
        sortResult[i] = index;
        tempArray[index] = 0;
        max = 0;
    }
}

int main()
{
    float     p[MAXSIZE], w[MAXSIZE], x[MAXSIZE];
    int     i = 0, n = 0;
    int     sortResult[MAXSIZE];

    getData(p, w, &n);

    for(i = 0; i < n; i++)
    {
        x[i] = p[i] / w[i];
    }

    SortIndex(x, sortResult, n);

    GREEDY(w, x, sortResult, n);

    output(x, n);

    return    0;
}

运行结果：
please input the total count of object: 3
Please input array of p :
40
35
20
Now please input array of w :
80
7
10
---------------------------------------------
x[0]        x[1]        x[2]        
0.03750     1.00000     1.00000     
----------------------------------------------