用贪心算法解背包问题（装载问题）

题目描述

给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第 i 种食品的最多拥有Wi 公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。

题目分析

分析：因为每一个物品都可以分割成单位体积，单位体积的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。方法如下： （1）先将单位块收益按从大到小进行排序； （2）从前到后考虑所有物品：a.如果可以完全放入，当前价值加上物品总价值，剩余体积减去物品总体积；b.如果可以部分放进，当前价值加上物品价值*剩余体积，使剩余体积为0.

程序代码

#include<iostream> using namespace std; /** * @author zjq~ * @time 2017/07/11 * @func 贪心算法解决背包问题 */ void Knapsack(float* w,float* v,float* x,int n,float c){ //默认传过来的物品是按照单位质量的价值从大到小排序的 for(int i=0;i<n;i++){ if(w[i]<c){ x[i]=1; c-=w[i]; }else{ x[i]=c/w[i]; break; } } } int main(){ int n=3; //物品总数 float c=50; //背包容量 float w[]={10,20,30}; //第 i+1 件物品的重量 float v[]={60,100,120}; //第 i+1 件物品的价值 float x[]={0,0,0}; //第 i+1 件物品选择的数量 初始都为 0 Knapsack(w,v,x,n,c); float sum=0; for(int i=0;i<n;i++){ cout<<"第"<<i+1<<"件物品装入"<<x[i]<<"件"<<endl; sum+=v[i]*x[i]; } cout<<"最大价值为："<<sum<<endl; }

最后

OJ地址：http://acm.hdu.edu.cn/showproblem.php?pid=2111 注意，这里在获取最优解的同时要记得按照单位体积的大小排序！