用贪心算法求解背包问题
1.贪心算法求解思路
基本思路：①建立数学模型来描述问题。②把求解的问题分成若干个子问题。③对每一子问题求解，得到子问题的局部最优解。④把子问题的解局部最优解合成原来解问题的一个解。
实现该算法的过程:从问题的某一初始解出发;while 能朝给定总目标前进一步 do;求出可行解的一个解元素;由所有解元素组合成问题的一个可行解。
2.利用贪心策略，需要解决的两个问题
确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：贪心选择性质和最优子结构性质。
① 贪心选择性质：可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。
② 最优子结构性质：原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。
背包问题
背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V?它是在1978年由Merkel和Hellman提出的。
题目：有N件物品和一个容量为V的背包。第i件物品的重量是w[i]，价值是v[i]。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。
#include<iostream>
usingnamespacestd;
#define MAXN 1001
doubler[MAXN];
intindex[MAXN],w1[MAXN];
intv1[MAXN],x[MAXN];
intvalues[MAXN],weights[MAXN];
int n,capacity;
/*
贪心算法--->背包问题
假设有一个背包最大可以装 150kg 物品
某物品 重量 价值(元) 性价比(单位重量的价格)
a 35kg 10 10/35
b 30kg 40 40/30
c 60kg 30 30/60
d 50kg 50 50/50
e 40kg 35 35/40
f 10kg 40 40/10
g 25kg 30 30/25
求：背包可以装入的最大价值
*/
intmain()
{
cin>>n>>capacity;
int maxValue=0;
for (int i = 0; i < n; i++)
cin>>weights[i];
for (int i =0;i<n; i++)
{
cin>>values[i];
r[i]=(double)values[i]/weights[i];
index[i]=i; //初始化各个物品的默认性价比排序
}
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(r[i]<r[j])
{
double temp=r[i];
r[i]=r[j];
r[j]=temp;
int t=index[i];
index[i]=index[j];
index[j]=t;
}
}
}
for(int i=0;i<n;i++)
{
w1[i]=weights[index[i]];
v1[i]=values[index[i]];
}
for(int i=0;i<n;i++)
{
if(w1[i]<=capacity)
{
x[i]=1; //表示将该物品装入背包
cout<<"物品："<<w1[i]<<" 被放进了"<<endl;
maxValue+=v1[i];
capacity-=w1[i];
}
}
for(int i=0;i<n;i++)
cout<<"总共放下的物品的数量为："<<x[i]<<endl;
cout<<"最大价值为："<<maxValue;
}