| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1560 人关注过本帖
标题:背包问题,高手进!!!1
只看楼主 加入收藏
andongtianzi
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2010-6-29
结帖率:40%
收藏
已结贴  问题点数:20 回复次数:10 
背包问题,高手进!!!1
【问题描述】
设有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的方案,
使选中的物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
【基本要求】
输入:物品数量n;背包的限制重量 ;每一件物品的重量w和价值p;
输出:选择的物品代号(方案);总重量;总价值;
(3)算法提示:(在此仅提示贪心法的核心思想)
n个物体和1个背包,物体 的重量 ,价值 ,背包的载荷能力 。即在
约束条件 下,使目标 最大。贪心法选择价值 与重量 比
大的物品装进背包。
    注:学生可选择其他算法实现。
搜索更多相关主题的帖子: 背包 
2010-06-29 21:19
andongtianzi
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2010-6-29
收藏
得分:0 
请不要在网上copy,我要独一无二的原版,谢谢!!!
2010-06-29 22:35
sunyh1999
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:14
帖 子:1178
专家分:3032
注 册:2009-5-17
收藏
得分:0 
这个不就是典型的作业贴么?

欢迎来到我的博客:http://blog..cn/noisunyuhong
2010-06-30 11:57
佳嘉
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:3
帖 子:534
专家分:1383
注 册:2009-11-8
收藏
得分:0 
回复 2楼 andongtianzi
只有你自己做的才是独一无二的
2010-06-30 17:06
andongtianzi
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2010-6-29
收藏
得分:0 
帮帮忙,急求高手相助!
2010-06-30 18:40
vs_inzaghi
Rank: 5Rank: 5
来 自:湖北
等 级:职业侠客
威 望:1
帖 子:303
专家分:364
注 册:2009-8-17
收藏
得分:0 
这算法已经很好了……嘿嘿……反正我还没想出更好的算法……

我很懒,但我讨厌别人说我懒……
2010-06-30 20:42
ZQDragon
Rank: 2
等 级:论坛游民
帖 子:30
专家分:39
注 册:2010-6-8
收藏
得分:20 
程序代码:
#include<stdio.h>
#include<windows.h>
#define N 5             //物品的数目
#define WEIHT 50         //背包的限重 

float maxratio= 0;       // 记录最大比值
float preratio= 0;       // 记录当前比值 

float WOH=0;             //记录最后包的价值
float WET=0;             //记录最后包的重量
float Preworth= 0;       // 记录当前背包总价值
float Preweight= 0;      //记录当前背包总重量 

float weight[N];         //记录物品的重量
float worth[N];          //记录物品的价值
bool  flag[N];           //记录物品是否被使用
bool   ans[N];            //记录物品的组合 

void MAXratio()
{
     int i , j ;
     for(i=0;i<N;++i)
     {
         Preweight+=weight[i];
         if(flag[i]==false&&Preweight<=WEIHT)
         {              
              Preworth+=worth[i];
              flag[i]=true;
              preratio=Preworth/Preweight;
              if(preratio>maxratio)
              {
                   WOH=Preworth;
                   WET=Preweight;
                   maxratio= preratio;
                   for(j=0;j<N;++j)
                   ans[j]=flag[j];
              }
              MAXratio() ;
              Preweight-=weight[i];
              Preworth-=worth[i];
              flag[i]=false;
         }
         else
              Preweight-=weight[i];    
     }
}

int main()
{
    int i ;
    printf("输入背包的重量和价值...\n\n");
    for(i=0;i<N;++i)
    {
         flag[i]=false;
         scanf("%f%f",&weight[i],&worth[i]);
    }
    MAXratio();
    printf("\t最大的比值是%f\n",maxratio) ;
    printf("\t包的重量是%f\n",WET);
    printf("\t包的价值是%f\n",WOH);
    printf("\n\n包的组合是:\n");
   
    for(i=0;i<N;++i)
    if(ans[i])
    printf("\t物品%d",i+1);
    printf("\n");
    system("pause");
    return 1;
}


               

      

其实你题目的要求有问题,因为按你题目的要求,答案很容易,因为结果物品肯定是一个,
应该是“在背包允许的情况下,求最大价值”;
这个程序的结果是按你题目做的,
但稍微改一点点,就可以按我的理解那样做了即“在背包允许的情况下,求最大价值”;
2010-07-01 00:21
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
程序代码:
#include<stdio.h>
int n=5,w[6]={0,2,2,6,5,4},v[6]={0,6,3,5,4,6},c=10;
int a[10][30];
int f(int n,int c)
{  int i,j,m;
  for(i=1;i<=n;i++)
    for(j=1;j<=c;j++)
      if(j<w[i])a[i][j]=a[i-1][j];
      else
    { m=a[i-1][j-w[i]]+v[i];
      if(m<a[i-1][j])m=a[i-1][j];
      a[i][j]=m;
    }
  return a[n][c];
}
void g(int n,int c,int x[])
{ int i,j;
  i=n,j=c;
  while(i>0&&j>0)
    if(a[i][j]>a[i-1][j])x[i]=1,i--,j-=w[i];
    else x[i]=0,i--;
}
int main()
{ int r,i,j,x[10];
  r=f(n,c);
  printf("  w   v \n");
  for(i=0;i<=n;i++)
    { printf("%3d %3d ",w[i],v[i]);
      for(j=0;j<=c;j++)
    printf("%3d",a[i][j]);
      printf("\n");
    }
  g(n,c,x);
  for(i=1;i<=n;i++)
    if(x[i])printf("%d",i);
  printf("\nr=%d\n",r);
  return 0;
}
2010-07-01 09:38
duanxianla
该用户已被删除
收藏
得分:0 
回复 3楼 sunyh1999
提示: 作者被禁止或删除 内容自动屏蔽
2010-07-01 09:52
andongtianzi
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2010-6-29
收藏
得分:0 
回复 8楼 Devil_W
这个貌似和题目有点出入吧,要求自己输入相关数据(如价值 重量),并得出结果
2010-07-01 18:38
快速回复:背包问题,高手进!!!1
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.054744 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved