背包问题贪心算法c语言
A. 背包问题的算法
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.
B. c语言贪心算法 背包问题
if(k!=i)
t=T[i];
T[i]=T[k];
T[k]=t;
交换操作的三步要用{}括起来,不然只有t=T[i];是if的执行语句
C. 用贪心算法解决背包问题
用贪心算法解决背包问题，首先要明白，结果不一定是全局最优的。对于贪心法而言，首先步骤是找到最优度量标准，我这里的算法采用的最优度量标准是： 收益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];}
D. 贪婪算法几个经典例子
问题一：贪心算法的例题分析 例题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 64输出一个解，返回上一步骤c--（x,y) ← c计算(x,y）的八个方位的子结点，选出那些可行的子结点循环遍历所有可行子结点，步骤c++重复2显然⑵是一个递归调用的过程，大致如下：C++程序： #define N 8void dfs(int x,int y,int count){ int i,tx,ty; if(count>N*N) { output_solution();输出一个解 return; } for(i=0; i>
问题二：收集各类贪心算法（C语言编程）经典题目 tieba./...&tb=on网络的C语言贴吧。 全都是关于C的东西。
问题三：几种经典算法回顾 今天无意中从箱子里发现了大学时学算法的教材《算法设计与分析》，虽然工作这么几年没在什么地方用过算法，但算法的思想还是影响深刻的，可以在系统设计时提供一些思路。大致翻了翻，重温了一下几种几种经典的算法，做一下小结。分治法动态规划贪心算法回溯法分支限界法分治法1）基本思想将一个问题分解为多个规模较小的子问题，这些子问题互相独立并与原问题解决方法相同。递归解这些子问题，然后将这各子问题的解合并得到原问题的解。2）适用问题的特征该问题的规模缩小到一定的程度就可以容易地解决该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题3）关键如何将问题分解为规模较小并且解决方法相同的问题分解的粒度4）步骤分解->递归求解->合并 divide-and-conquer(P) { if ( | P | >
问题四：求三四个贪心算法的例题（配源程序代码，要带说明解释的）！非常感谢 贪心算法的名词解释
ke./view/298415
第一个贪心算法 （最小生成树）
ke./view/288214
第二个贪心算法 （Prim算法）
ke./view/671819
第三个贪心算法 （kruskal算法）
ke./view/247951
算法都有详细解释的
问题五：求 Java 一些经典例子算法 前n项阶乘分之一的和
public class jiecheng {
public static void main(String[] args)
{
double sum=0;
double j=1;
int n=10;
for(int i=1;i 问题六：关于编程的贪心法 定义
所谓贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
[编辑本段]贪心算法的基本思路
1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。
[编辑本段]例题分析
[背包问题]有一个背包，背包容量是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最大 约束条件是装入的物品总重量不超过背包容量：∑wi>
问题七：求解一贪心算法问题 最快回答那个不懂别乱说，别误人子弟。
这题标准的贪心算法，甚至很多时候被当做贪心例题
要求平均等待时间，那么就得用 总等待时间 / 人数
所以只用关心总等待时间，
如果数据大的在前面，那么后面必然都要加一次这个时间，所以按从小到大排。
给你写了个，自己看吧。
#include stdafx.h
#include
#include
#include
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
int n;
float arr[105];
cin >> n;
for(int i = 0; i > arr[i];
sort(arr, arr+n);
int tnow = 0;
int tmax = 0;
for(int i = 0; i 问题八：分治算法的应用实例 下面通过实例加以说明： 给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。另外一种方法就是利用分而治之方法。假如把1 6硬币的例子看成一个大的问题。第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把1 6个硬币的问题分成两个8硬币的问题来解决。第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。这样，1 6硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则，继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此再把它分成两组，每组有4个硬币。称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。 在n个元素中找出最大元素和最小元素。我们可以把这n个元素放在一个数组中，用直接比较法求出。算法如下：void maxmin1(int A[],int n,int *max,int *min){ int i;*min=*max=A[0];for(i=0;i *max) *max= A[i];if(A[i] >
问题九：回溯算法的典型例题 八皇后问题：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
问题十：什么是算法，都什么，举个例子，谢谢 算法就是解决问题的具体的方法和步骤，所以具有以下性质：
1、有穷性： 一个算法必须保证执行有限步之后结束（如果步骤无限，问题就无法解决）
2、确切性：步骤必须明确，说清楚做什么。
3、输入：即解决问题前我们所掌握的条件。
4、输出：输出即我们需要得到的答案。
5、可行性：逻辑不能错误，步骤必须有限，必须得到结果。
算法通俗的讲：就是解决问题的方法和步骤。在计算机发明之前便已经存在。只不过在计算机发明后，其应用变得更为广泛。通过简单的算法，利用电脑的计算速度，可以让问题变得简单。
E. 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(
F. 关于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;
}
}
G. c语言背包问题
算法分析：
使用贪心策略求解此类问题时，首先要选出最优的度量标准。
可供选择的度量标准有三种：价值，容量，单位价值（v/w，价值/重量）。
显然，价值高的物品容量可能太大，容量大的物品价值也可能很低。最优的度量标准是单位价值。
背包困液问题算法思路：
1、将各个物品按照单位价值由高到低排序；
2、取价值最高者放入背包；
3、计算背包的剩余空间；
4、重复2-3步，直到背包剩余容量=0或者物品全部装入背包为止（对于0-1背包，终止条件为背包剩余容量无法装入任意一件物品或者物品全部装入背包）。
#include<stdio.h>
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已经按照单位价值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包问题
* n:物品个数
* c：背包容量
* v[]:每个物品的价值
* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始状态，所有物品都没有被汪行物放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
if(i<=n)//还可以放入一个物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包问题
* n:物品个数
* c：背包容量
* v[]:每个物品的价值
* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始状态带团，所有物品都没有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
}
#include<stdio.h>
void package(int n,float c,float v[],float w[],float x[]);
void package0_1(int n,float c,float v[],float w[],float x[]);
int main(void)
{
int n = 3;
float c = 20;
float v[] = {24,15,25};
float w[] = {15,10,18};//已经按照单位价值降序排列
float *x;
x = (float*)malloc(sizeof(float)*n);
printf("******背包*******\n");
package(n,c,v,w,x);
printf("*******0-1背包******\n");
package0_1(n,c,v,w,x);
system("PAUSE");
}
/*
* 背包问题
* n:物品个数
* c：背包容量
* v[]:每个物品的价值
* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）
*/
void package(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
if(i<=n)//还可以放入一个物品的一部分
{
x[i] = c/w[i];
printf("放入第%d件物品的%f部分.背包剩余容量为0.\n",(i+1),w[i]*x[i]);
}
}
/*
* 0-1背包问题
* n:物品个数
* c：背包容量
* v[]:每个物品的价值
* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）
* x[]:物品是否放入背包（0表示不放，1表示全部放入）
*/
void package0_1(int n,float c,float v[],float w[],float x[])
{
int i;
for(i=0;i<n;i++)
{
x[i] = 0;//初始状态，所有物品都没有被放入背包
}
for(i=0;i<n;i++)
{
if(w[i] > c)
{
break;
}
x[i] = 1;
c = c - w[i];
printf("放入第%d件物品，背包剩余容量%f.\n",(i+1),c);
}
}
H. 关于一道C语言的背包问题，用的是贪心算法
//输入物品的信息
void inputstone(stone *bag,int num)
{
for(int i=0;i<num;i++)
{
bag[i].name=i+1;//物品的名字
printf("请输入第%d号物品的重量:",i+1);
scanf("%d",&bag[i].weight);
if (bag[i].weight<=0)
{printf("物品的重量必须大于0!\n");}
printf("请输入第%d号物品的价值:",i+1);
scanf("%f",bag[i].benefit);
if (bag[i].benefit<=0)
{printf("物品的价值必须大于0!\n");}
bag[i].weight_t=bag[i].weight;
}
}
这部分中的
scanf("%f",&bag[i].benefit); //缺少&
把这行加上&就对了
I. 求完全背包问题的代码(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求和十效率降低。不过这确实是一种很新颖的算法。