❶ 0/1背包问题能不能使用贪心法解决
贪心算法解决背包问题有几种策略：
(i)一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
(ii)另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
(iii)还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。
有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。虽然按pi /wi 非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。
而且这是解决普通背包问题的最优解，因为在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
❷ 证明题：用解背包问题的贪心算法解0-1背包问题时不一定得到最优解 急求！！
贪心算法总是作出在当前看来是最好的选择，即贪心算法并不从整体最优解上加以考虑，它所作出的选择只是在某种意义上的局部最优解。
背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。
用贪心算法求解背包问题的步骤是，首先计算每种物品单位重量的价值vi/wi；然
后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总量未超过c，则选择单位重量价值次高的物
品并尽可能多地装入背包。依此策略一直进行下去，直到背包装满为止。
在最后一步包装不下时可能会分割物品，而0-1背包问题不能分割物品，故不一定得到最优解。
取一反例即可说明
❸ 请教我用python的贪心法做0/1背包问题
动态规划，可以给你说下思路。
我们用一个二维的矩阵A来存储中间结果，A[i][j]代表前i个物体装入容量为j的背包时可以得到的最优解，相当于是原问题的一个子问题，然后我们就可以写出递推式来更新这个矩阵，具体可以参考下详细的讲解，网上的博客非常多不用我再写一遍。
比如这种：http://zh.wikipedia.org/zh-cn/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98
先自己读一遍吧，有问题可以再问。
❹ 用贪心算法解决背包问题
用贪心算法解决背包问题，首先要明白，结果不一定是全局最优的。对于贪心法而言，首先步骤是找到最优度量标准，我这里的算法采用的最优度量标准是： 收益p/重量w 的值最大者优先放入背包中，所以有算法如下：void GreedyKnapsack(float * x){ //前置条件：w[i]已按p[i]/w[i]的非增次序排列 float u=m; //u为背包剩余载重量，初始时为m for(int i=0;i<n;i++) x[i]=0; //对解向量x初始化 for(i=0;i<n;i++){ //按最优度量标准选择的分量 if(w[i]>u) break; x[i]=1.0; u=u-w[i]; } if(i<n) x[i]=u/w[i];}
❺ 01背包问题
能不能用性价比来做呢
动态规划看不懂啊
----------------------------------------------------------------------
如果不是0-1问题的话，当然可以通过比较性价比来做，这时候可考虑用贪心算法；但如果是0-1问题的话就不能单纯“用性价比来做”了，因为有可能背包空出一大块。举个简单的例子：一个背包的容量是10KG，
物品A重7KG，价值为14元，
物品B重6KG，价值为11元，
物品C中4KG，价值为7元，
从性价比来看，A最高，但是将A放到背包里以后，无法放进其他物品了，此时总价值为14元；显然，本问题的最佳方案为将B、C放入背包，总价值为18元。
这就是0-1背包问题为什么能用动态规划算法，而不能用贪心算法的原因。共同学习:-D
❻ 贪心算法解决特殊0-1背包问题
void 0_1_Knapsack(float w[], int n, float c,int x[]) //w[]为每个物品的重量，c为背包容量
{
int i;
for(i=1;i<=n;i++) x[i]=0;
for(i=1;i<=n;i++)
{
if(w[i]>c) break;
x[i]=1;
c-=w[i];
}
}
❼ C语言贪心算法 背包问题
if(k!=i)
t=T[i];
T[i]=T[k];
T[k]=t;
交换操作的三步要用{}括起来,不然只有t=T[i];是if的执行语句