wdjh.net
当前位置:首页 >> 01背包问题贪心算法 >>

01背包问题贪心算法

一.动态规划求解0-1背包问题 /************************************************************************/ /* 0-1背包问题: /* 给定n种物品和一个背包 /* 物品i的重量为wi,其价值为vi /* 背包的容量为c /* 应如何选择装入背包的物品,使得装...

贪心法是每一步的最优解就是整体的最优解。 0-1背包是属于动态规划,每一步的解不一定导致整体的最优解。 对于你问 “什么样的题用0-1背包问题作” 就是需要你自己做题来体会了。 如果全局的最优解可以用分布的最优解求出来,就用贪心, 如果不是...

这种规则,价值最大的物品首先被装入(假设有足够容量),然后是下一个价值最大的物品,如此继续下去。这种策略不能保证得到最优解。例如,考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时,获得的解为x= [ 1 , 0 , 0 ]...

因为贪心算法的正确性无法被证明,而且有反例

已发~·

[背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大校 要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。 物品 A B C D E F G 重量 35 30 60 50 40 10 25 价值 10 40 30 50 35 40 30 分析: 目标函数: ∑pi最...

排序应该下面这样写 for(i=0;i

你这个是部分背包么?也就是说物品可以随意分割? 那么可以先算出单位重量物品的价值,然后只要从高价值到低价值放入就行了,按p[i]/w[i]降序排序,然后一件一件加,加满为止! 贪心的思路是:加最少的重量得到更大的价值! 算出单位价值为{6,4,...

#include #include #define MAXWEIGHT 20 #define n 3 float pw[n]={0},x[n]={0}; int w[n]={0},p[n]={0}; void sort(int p[],int w[]) { int temp1,temp2; float temp; int i,j; for(i=0;i

是你的冒泡排序出了问题~ 你吧 原来的1-2-3号按照东西的价值重新排列现在的1-2-3对应原来的2-1-3了 所以 你输出的时候是按 1-2-3输出的话 就等于第一个是原来的X2 第二个是X1第三个是X3 而且你的冒泡排序用错了 只比较了 P[0]/K[0]和P[1]/K[1] P...

网站首页 | 网站地图
All rights reserved Powered by www.wdjh.net
copyright ©right 2010-2021。
内容来自网络,如有侵犯请联系客服。zhit325@qq.com