北京杰诚 做网站,西安网站建设小程序开发,成都网站建设金网科技,首尔面积0-1背包问题#xff1a; 前提#xff1a;给定n种物品和一个背包。物品i的重量是Wi#xff0c;其价值为Vi#xff0c;背包的容量为C。 问题#xff1a;应如何选择装入背包的物品#xff0c;使得装入背包中物品的总价值最大?
背包问题#xff1a; 与0-1背包问题类似 前提给定n种物品和一个背包。物品i的重量是Wi其价值为Vi背包的容量为C。 问题应如何选择装入背包的物品使得装入背包中物品的总价值最大?
背包问题 与0-1背包问题类似所不同的是在选择物品i装入背包时可以选择物品i的一部分而不一定要全部装入背包1≤i≤n。
贪心算法总是做出在当前看来是最好的选择也就是说贪心算法并不从整体最优上加以考虑所做出的的选择只是某种意义上的局部最优选择 虽然贪心算法不是对所有的问题都能得到整体最优解但对范围相当广的许多问题都能产生最优解即使贪心算法不能得到整体最优解但其最终结果却是最终结果却是最优解的很好的近似解。
注意不要用if else
#includeiostream
#includealgorithm
#includecstring
using namespace std;typedef struct Node
{float value;float weight;float vw;//单位重量的价值
}node;
bool cmp(node x,node y)
{if(x.vwy.vw)//从大到小排序 return true;elsereturn false;
}
void knaspsack(int n,float capacity,float *value,float *weight,float *result)
{Node node[n1];for(int i1;in;i){node[i].valuevalue[i];node[i].weightweight[i];node[i].vw(float)node[i].value/node[i].weight;}sort(node1,noden1,cmp);for(int i1;in;i){value[i]node[i].value;coutvalue[i] ;weight[i]node[i].weight;coutweight[i] ;coutnode[i].vwendl;}float ccapacity;int i;for(int i1;in;i){if(cweight[i])break;//这里不能使用if else result[i]1;cc-weight[i];}if(in){ result[i]c/weight[i]; }
}
void knapsack(int n,float M,float v[],float w[],float x[])
{ int i; //物品整件被装下 for(i1;in;i){ if(w[i]M) break; x[i]1; M-w[i]; } //物品部分被装下 if(in) x[i]M/w[i];
}
int main()
{cout输入背包中物品的种类;int n;cinn; cout输入背包的容量;float capacity;cincapacity; cout输入物品对应的价格;float value[n1]; for(int i1;in;i){cinvalue[i];}cout输入物品对应的重量;float weight[n1];for(int i1;in;i){cinweight[i];}float result[n1];for(int i1;in;i){result[i]0;}//knaspsack(n,capacity,value,weight,result);knapsack(n,capacity,value,weight,result);for(int i1;in;i){coutresult[i] ;}return 0;} 贪心算法解决背包问题的主要时间用在了将其各种物品按其单位重量的价值从小到大排序 O(n*logn)
