贪心算法求解背包问题-蒲公英云

贪心算法求解背包问题

问题：给定n个物品和一个容量为C的背包，物品i的重量为w 其价值为v。背包问题就是如何如何选择背包的物品，使装入背包中的物品的总价值是最大的，注意和0/1背包问题的区别，在背包问题中可以将某种物品的一部分装入背包，不可以重复装入。但是在0/1背包问题中，只有装入或者不装入两种结果。

#include<iostream>
using namespace std;
int KanpSack(int w[],int v[],int C) {
    double x[10] = {0};
    int maxValue = 0;
    int i = 0;
    do {
        x[i] = 1;
        maxValue+=v[i];
        C = C-w[i];
        i++;
    } while(w[i]<C);
//    for(int i =0 ; w[i]<C;i++){
//        x[i] = 1;
//        maxValue+=v[i];
//        C =C-w[i];
//    }
    x[i] = (double)C/w[i];
    maxValue+=x[i]*w[i];
    return maxValue;
}
int main() {
    int arrayw[10]= {9,8,7,6,5,4,3,2,1,0};
    int arrayv[10]= {9,8,7,6,5,4,3,2,1,0};
    int cw = 60;
    int rel =  KanpSack(arrayw,arrayv,cw);
    cout<<"这个背包的价值是："<<rel<<endl;
    return 0;
}

这个代码简单的实现了背包问题的结果可以尽可能多的增加了背包的价值，从某种意义上讲，从最简单的方面实现了背包问题。首先满足价值和重量的递减排序，其次我们看到背包容量的大小就是60。其实所有的方法都可以在这个代码的基础之上加以修改，举个例子，当用户自己输入一组数据的时候由于是乱序的所以，我们可以利用一个简单的排序算法实现对用户输入的排序