贪心算法背包问题c

Ⅰ 贪心算法的例题分析

例题1、
[0-1背包问题]有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
价值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目标函数：∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M(M=150）
⑴根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
⑵每次挑选所占重量最小的物品装入是否能得到最优解？
⑶每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
⑴贪心策略：选取价值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
⑵贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
⑶贪心策略：选取单位重量价值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
【注意：如果物品可以分割为任意大小，那么策略3可得最优解】
对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。
但是，如果题目是如下所示，这个策略就也不行了。
W=40
物品：A B C
重量：25 20 15
价值：25 20 15
附：本题是个DP问题，用贪心法并不一定可以求得最优解，以后了解了动态规划算法后本题就有了新的解法。
例题2、
马踏棋盘的贪心算法
123041-23 XX
【问题描述】
马的遍历问题。在8×8方格的棋盘上，从任意指定方格出发，为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
【初步设计】
首先这是一个搜索问题，运用深度优先搜索进行求解。算法如下：
⒈ 输入初始位置坐标x,y；
⒉ 步骤 c:
如果c> 64输出一个解，返回上一步骤c--
（x,y) ← c
计算(x,y）的八个方位的子结点，选出那些可行的子结点
循环遍历所有可行子结点，步骤c++重复2
显然⑵是一个递归调用的过程，大致如下：
C++程序： #defineN8voiddfs(intx,inty,intcount){inti,tx,ty;if(count>N*N){output_solution();//输出一个解return;}for(i=0;i<8;i++){tx=hn[i].x;//hn[]保存八个方位子结点ty=hn[i].y;s[tx][ty]=count;dfs(tx,ty,count+1);//递归调用s[tx][ty]=0;}}Pascal程序： ProgramYS;ConstFXx:array[1..8]of-2..2=（1,2,2,1,-1,-2,-2,-1）；FXy:array[1..8]of-2..2=（2,1,-1,-2,-2,-1,1,2）；VarRoad:array[1..10,1..10]ofinteger;x,y,x1,y1,total:integer;ProcereFind(x,y:integer);varNx,Ny,i:integer;BeginFori:=1to8dobegin{8个方向}If(x+FXx[i]in[1..8])and(y+FXy[i]in[1..8])Then{确定新坐标是否越界}IfRoad[x+Fxx[i],y+Fxy[i]]=0Thenbegin{判断是否走过}Nx:=x+FXx[i];Ny:=y+FXy[i];Road[Nx,Ny]:=1;{建立新坐标}If(Nx=x1）and(Ny=y1）Theninc(total)elseFind(Nx,Ny);{递归}Road[Nx,Ny]:=0{回朔}endendEnd;BEGIN{Main}Total:=0;FillChar(Road,sizeof(road),0);Readln(x,y);{读入开始坐标}Readln(x1,y1）；{读入结束坐标}If(x>10）or(y>10）or(x1>10）or(y1>10）Thenwriteln('Error'){判断是否越界}ElseFind(x,y);Writeln('Total:',total){打出总数}END.这样做是完全可行的，它输入的是全部解，但是马遍历当8×8时解是非常之多的，用天文数字形容也不为过，这样一来求解的过程就非常慢，并且出一个解也非常慢。
怎么才能快速地得到部分解呢？
【贪心算法】
其实马踏棋盘的问题很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一个有名的算法。在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发式算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略，至于什么问题需要什么样的贪心策略是不确定的，具体问题具体分析。实验可以证明马遍历问题在运用到了上面的贪心策略之后求解速率有非常明显的提高，如果只要求出一个解甚至不用回溯就可以完成，因为在这个算法提出的时候世界上还没有计算机，这种方法完全可以用手工求出解来，其效率可想而知。

Ⅱ 动态规划背包问题与贪心算法哪个更优

首先这两个算法是用来分别解决不同类型的背包问题的，不存在哪个更优的问题。
当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大到小取即可。
当一件背包物品不可分割的时候，（因为不可分割，所以就算按物品的单位体积的价值大的先取也不一定是最优解）此时使用贪心是不对的，应使用动态规划。

Ⅲ 求完全背包问题的代码(C语言或C++版)或算法

背包问题小结- []2006-07-28

做到背包问题觉得很有意思，写写看看。
完全背包问题可以用贪心算法。
代码如下：

program bag1;
const maxn=10;
var
goods:array[1..maxn,1..3] of integer;
s:array[1..maxn] of real;
i,j:integer;
m,n:integer;
y:integer;
x:real;
function max:integer;
var m:real;
i,j:integer;
begin
m:=0;
for i:=1 to n do
if (goods[i,3]=0) and (m max:=j;
end;

procere choose;
var i,j:integer;

begin
while y begin
if y begin
i:=max;
if m>=y+goods[i,1] then begin goods[i,3]:=1;x:=x+goods[i,2];y:=y+goods[i,1];end else
begin
x:=x+(m-y)*s[i];
y:=m;
end;
end;
end;
end;

begin
fillchar(goods,sizeof(goods),0);
assign(input,'b.txt');
reset(input);
readln(m,n);
for j:=1 to n do
read(goods[j,1]);
readln;
for j:=1 to n do
read(goods[j,2]);
for j:=1 to n do
s[j]:=goods[j,2]/goods[j,1];

close(input);
choose;
writeln(x:5:2);
end.
编得不是很好 ^-^ 献丑了。

我来说说0/1背包问题。
状态：当前物品n
算符：j=0（当前物品不放入背包） 或 j=1（当前物品放入背包）
这就很好说了，还是把yes函数一改，问题OK了。
代码如下：

program bag2;
const maxn=10;
var i:integer;
goods:array[1..maxn,1..3] of integer;{原始数据}
s:array[1..maxn] of integer;{当前的状态}
r:array[1..maxn] of integer;{当前的总质量}
m:integer;{背包容量}
max:integer;{物品个数}
procere try(n:integer);
var j:integer;

{function yes:boolean;
var k:integer;
t:integer;
mn:integer;
begin
mn:=0;
t:=goods[n,3];
goods[n,3]:=j;
for k:=1 to n do
if goods[k,3]=1 then inc(mn,goods[k,1]);
goods[n,3]:=t;
if mn>m then yes:=false else yes:=true;
end;}

begin
if n=max+1 then begin if x for i:=1 to max do s[i]:=goods[i,3]; {保存最优解}end
end else
begin
if r[n-1]>m then exit;{已超过背包总容量}
for j:=1 downto 0 do
begin
if j=1 then r[n]:=r[n-1]+goods[n,1];
if j=0 then r[n]:=r[n]-goods[n,1];
if {yes}r[n]<=m then begin goods[n,3]:=j;try(n+1);goods[n,3]:=0;end
end;
end;
end;

begin
assign(input,'b.txt');
reset(input);
readln(m,max);
for i:=1 to max do
read(goods[i,1]);
readln;
for i:=1 to max do
read(goods[i,2]);
close(input);
try(1);
for i:=1 to 7 do
write(s[i]:3);
writeln;
writeln(x);
end.

用yes 函数要从头到当前求已装入背包物品的总质量，时间效率不高。所以我们引入r[n]数组来记录当前背包总质量（很好用！）注意用r[n-1]>m来做剪枝，以再次提高时间效率。

DC跟我说可以用二进制解此类问题。我觉得很有创意，也说说。比如8个物品，每个物品有0/1两种状态所以我们从(00000000)(二进制 )到（11111111）（二进制）循环即可。然后在分离十进制数对应起来即可。但在实际的操作中发现效率比回溯还低，我想有两方面的原因：1、显而易见，不可能做剪枝。2、每一次结果都要从1到8求和十效率降低。不过这确实是一种很新颖的算法。

Ⅳ C语言 贪心算法求背包问题

是你的冒泡排序出了问题~

你吧 原来的1-2-3号按照东西的价值重新排列现在的1-2-3对应原来的2-1-3了
所以 你输出的时候是按 1-2-3输出的话 就等于第一个是原来的X2 第二个是X1第三个是X3
而且你的冒泡排序用错了 只比较了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去学校帮你重新改改 我家的机器没有C++
周一晚上我会上传答案~我最近正好也要做算法的作业~
#include <stdio.h>
#include <math.h>
#define N 50

float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放单位价值量大的物体，再考虑小的物体*/
{
int i;
float maxprice;
for (i = 0; i < n; i++)
x[i] = 0;
i = 0;
maxprice=0;
while (i < n && w[i] < M)
{
M=M-w[i];
x[i] =w[i]; /* 表示放入数量 */
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if (i < n &&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}

int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(

Ⅳ 贪心算法 部分背包问题

这道题是dp的思想啦，动态规划

(1)背包问题最优值的结构

动态规划的逆向思维法的第一步是刻画一个最优值的结构，如果我们能分析出一个问题的最优值包含其子问题的最优值，问题的这种性质称为最优子结构。一个问题的最优子结构性质是该问题可以使用动态规划的显着特征。

对一个负重能力为m的背包，如果我们选择装入一个第 i 种物品，那么原背包问题就转化为负重能力为 m-w[i] 的子背包问题。原背包问题的最优值包含这个子背包问题的最优值。若我们用背包的负重能力来划分状态，令状态变量s[k]表示负重能力为k的背包，那么s[m]的值只取决于s[k](k≤m)的值。因此背包问题具有最优子结构。

(2)递归地定义最优值

动态规划的逆向思维法的第二步是根据各个子问题的最优值来递归地定义原问题的最优值。对背包问题而言，有状态转移方程：

／max{s[k-w[i]]+v[i]}(其中1≤i≤n，且k-w[i]≥0)

s[k]= 若k>0且存在1≤i≤n使k-w[i]≥0，

＼ 0 否则。

有了计算各个子问题的最优值的递归式，我们就可以直接编写对应的程序。下述的函数knapsack是输入背包的负重能力k，返回对应的子背包问题的最优值s[k]：

Ⅵ 用贪心算法能求解背包问题吗为什么,理由是什么

一般的贪心策略都会造成解的丢失,动态规划则是相当于枚举了所有的解.

如果你有一个很好的贪心策略,背包问题也能用贪心策略来解决.但是,你是很难找到一个很好的贪心策略的.

Ⅶ 关于C++ 01背包问题

1.摘要

以背包问题为例，介绍了贪心法与动态规划的关系以及两个方案在解决背包问题上的比较。贪心法什么时候能取到最优界并无一般理论，但对于普通背包问题我们有一个完美的结果——贪心法可取到最优解。介绍了其它一些对背包问题的研究或者拓展。

2.介绍

贪心算法是我们在《算法设计技巧与分析》这门课中所学习到的几种重要的算法之一，顾名思义，贪心算法总是作出在当前看来最好的选择。也就是该算法并不从整体最优考虑，它所作出的选择只是在某种意义上的从局部的最优选择，寻找到解决问题的次优解的方法。虽然我们希望贪心算法得到的最终结果也是整体最优的，但是在某些情况下，该算法得到的只是问题的最优解的近似。

3.算法思想:

贪心法的基本思路：

——从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。

该算法存在问题：

1.不能保证求得的最后解是最佳的；

2.不能用来求最大或最小解问题；

3.只能求满足某些约束条件的可行解的范围。

实现该算法的过程：

在约束下最大。

(2)动态规划解决方案：是解决0/1背包问题的最优解

(i)若i=0或j=0,V[i,j] = 0

(ii)若j<si, V[i,j] = V[i-1,j](仅用最优的方法，选取前i-1项物品装入体积为j的背包，因为第i项体积大于j,装不下这一项，所以背包里面的i-1项就达到最大值)

(iii)若i>0和j>=si, Max{V[i-1,j],V[i-1,j-si]+vi} (第一种情况是包中的i-1项已经达到最大值，第二种情况是i-1项占j-si的体积再加上第i项的总的价值，取这两种情况的最大值。)

//sj和vj分别为第j项物品的体积和价值，C是总体积限制。

//V[i,j]表示从前i项{u1,u2,…,un}中取出来的装入体积为j的背包的物品的最大//价值。[13]

（3）贪心算法解决背包问题有几种策略：

(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。

如图1，大体上说明了动态规划解决的0／1背包问题和贪心算法解决的问题之间的区别，

图1

（4）贪心算法解决背包问题的算法实现：

代码如下：

#include<iostream.h>
structgoodinfo
{
floatp;//物品效益
floatw;//物品重量
floatX;//物品该放的数量
intflag;//物品编号
};//物品信息结构体
voidInsertionsort(goodinfogoods[],intn)
{//插入排序，按pi/wi价值收益进行排序，一般教材上按冒泡排序
intj,i;
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while(goods[0].p>goods[i].p)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
}//按物品效益，重量比值做升序排列
voidbag(goodinfogoods[],floatM,intn)
{

floatcu;
inti,j;
for(i=1;i<=n;i++)
goods[i].X=0;
cu=M;//背包剩余容量
for(i=1;i<n;i++)
{
if(goods[i].w>cu)//当该物品重量大与剩余容量跳出
break;
goods[i].X=1;
cu=cu-goods[i].w;//确定背包新的剩余容量
}
if(i<=n)
goods[i].X=cu/goods[i].w;//该物品所要放的量
/*按物品编号做降序排列*/
for(j=2;j<=n;j++)
{
goods[0]=goods[j];
i=j-1;
while(goods[0].flag<goods[i].flag)
{
goods[i+1]=goods[i];
i--;
}
goods[i+1]=goods[0];
}
///////////////////////////////////////////
cout<<"最优解为:"<<endl;
for(i=1;i<=n;i++)
{
cout<<"第"<<i<<"件物品要放:";
cout<<goods[i].X<<endl;
}
}
voidmain()
{
cout<<"|--------运用贪心法解背包问题---------|"<<endl;
intj,n;floatM;
goodinfo*goods;//定义一个指针
while(j)
{
cout<<"请输入物品的总数量：";
cin>>n;
goods=newstructgoodinfo[n+1];//
cout<<"请输入背包的最大容量：";
cin>>M;
cout<<endl;
inti;
for(i=1;i<=n;i++)
{goods[i].flag=i;
cout<<"请输入第"<<i<<"件物品的重量:";
cin>>goods[i].w;
cout<<"请输入第"<<i<<"件物品的效益:";
cin>>goods[i].p;
goods[i].p=goods[i].p/goods[i].w;//得出物品的效益，重量比
cout<<endl;

}
Insertionsort(goods,n);
bag(goods,M,n);
cout<<"press<1>torunagian"<<endl;
cout<<"press<0>toexit"<<endl;
cin>>j;
}
}

Ⅷ 背包问题的算法

3.2 背包问题
背包问题有三种

1.部分背包问题

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。

解决问题的方法是贪心算法:将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.

2.0/1背包

一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

<1>分析说明:

显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).

程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数

设 f(i，x)表示前i件物品，总重量不超过x的最优价值

则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））

f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;

动态规划方法(顺推法)程序如下:

程序如下：

program knapsack02;
const maxm=200;maxn=30;
type ar=array[1..maxn] of integer;
var m,n,j,i:integer;
c,w:ar;
f:array[0..maxn,0..maxm] of integer;
function max(x,y:integer):integer;
begin
if x>y then max:=x else max:=y;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
for i:=1 to m do f(0,i):=0;
for i:=1 to n do f(i,0):=0;

for i:=1 to n do
for j:=1 to m do
begin
if j>=w[i] then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
else f[i,j]:=f[i-1,j];
end;
writeln(f[n,m]);
end.

使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。

3.完全背包问题

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,

每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.

求旅行者能获得的最大总价值。

本问题的数学模型如下：

设 f(x)表示重量不超过x公斤的最大价值，

则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n

程序如下:（顺推法）

program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
f:array[0..maxm] of integer;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
f(0):=0;
for i:=1 to m do
for j:=1 to n do
begin
if i>=w[j] then t:=f[i-w[j]]+c[j];
if t>f[i] then f[i]:=t
end;
writeln(f[m]);
end.

Ⅸ 贪心算法解决0-1背包问题得到的解通常是最优解或者近似最优解吗

这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑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], 比最优解