出一个简单的算法题，测测论坛的整体水平 - C语言论坛

| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 |

编程论坛 → 开发语言 → 『 C语言论坛』 → 出一个简单的算法题，测测论坛的整体水平

我的收件箱(0)

欢迎加入我们，一同切磋技术

共有 7364 人关注过本帖， 7 人收藏

标题：出一个简单的算法题，测测论坛的整体水平

只看楼主加入收藏

刘定邦

等　级：青峰侠
帖　子：687
专家分：1570
注　册：2010-9-21

第 11 楼

得分:0

以下是引用醉酒大哥在2011-1-1 13:54:18的发言：

看招
#include
#define M 17
#define O (i*b[0]+j*b[1]+k*b[2]+m*b[3]+n*b[4])
#define P (a[0]*i+a[1]*j+a[2]*k+a[3]*m+a[4]*n)
void main()
{
    int a[5]={3,4,7,8,9},b[5]={4,5,10,11,13},i,j,k,m,n,max=0;
    for(i=0;i<=M/a[0];i++)
      for(j=0;j<=M/a[1];j++)
        for(k=0;k<=M/a[2];k++)
          for(m=0;m<=M/a[3];m++)
            for(n=0;n<=M/a[4];n++)
            {
                if(P<=M)
                 {
                   if(max<=O)
                   {
                        max=O;
                        printf("i,j,k,m,n fen bie wei:%d,%d,%d,%d,%d ,zui da zhi:%d\n",i,j,k,m,n,max);
                    }
                  }
            }
    getch();
}

这个运行怎么多了最大为0和13这两种情况呢？

图片附件: 游客没有浏览图片的权限，请登录或注册

2011-01-02 08:55

sunyh1999

等　级：版主
威　望：14
帖　子：1178
专家分：3032
注　册：2009-5-17

第 12 楼

得分:5

背包....

欢迎来到我的博客：http://blog..cn/noisunyuhong

2011-01-02 12:21

sunyh1999

等　级：版主
威　望：14
帖　子：1178
专家分：3032
注　册：2009-5-17

第 13 楼

得分:0

回复 11楼刘定邦

用枚举，你厉害

欢迎来到我的博客：http://blog..cn/noisunyuhong

2011-01-02 12:22

BlueGuy

等　级：版主
威　望：29
帖　子：4476
专家分：4055
注　册：2009-4-18

第 14 楼

得分:0

以下是引用sunyh1999在2011-1-2 12:21:47的发言：

背包....

sunyh1999 版主好久不见，算法一定更上一层楼了吧

我就是真命天子，顺我者生，逆我者死！

2011-01-02 12:24

拂晓晨曦

等　级：论坛游民
帖　子：87
专家分：44
注　册：2010-10-31

第 15 楼

得分:5

回复 8楼一世哀伤

你也是西电的呀。。嘿嘿。。。

2011-01-02 12:24

sunyh1999

等　级：版主
威　望：14
帖　子：1178
专家分：3032
注　册：2009-5-17

第 16 楼

得分:0

#include <stdio.h>
#include <stdlib.h>
FILE *fin,*fout;
void file_start()
{
if((fin=fopen("bag.in","r"))==NULL)
{
  printf("Cannot open this file!\n");
  getchar();
  exit(0);
}
if((fout=fopen("bag.out","w"))==NULL)
{
  printf("Cannot open this file!\n");
  getchar();
  exit(0);
}
}
int max(int a,int b)
{
if(a>b)
  return a;
else
  return b;
}
int main()
{
int w[100]={0},v[100]={0},dp[10000]={0},m,n;
short int g[1000][1000]={0};
int i,j,sum=0;
file_start();
fscanf(fin,"%d %d",&m,&n);
for(i=0;i<n;i++)
fscanf(fin,"%d %d",&w[i],&v[i]);
for(i=0;i<n;i++)
for(j=m;j>=w[i];j--)
{
  //dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
  //g[i][j]=1;//记录选了第i件物品
  if(dp[j-w[i]]+v[i]>dp[j])
  {
   dp[j]=dp[j-w[i]]+v[i];
   g[i][j]=1;
  }
}
fprintf(fout,"%d",dp[m]);
//开始递推
fprintf(fout,"\n");
sum=m;
for(i=n;i>=0;i--)
{
  if(g[i][sum]==1)
  {
   fprintf(fout,"%d ",i+1);
   sum=sum-w[i];
  }
}
system("pause");
return 0;
}

欢迎来到我的博客：http://blog..cn/noisunyuhong

2011-01-02 12:39

StarWing83

来　自：仙女座大星云
等　级：贵宾
威　望：19
帖　子：3951
专家分：748
注　册：2007-11-16

第 17 楼

得分:5

完全背包。

需要两次计算，第一次算最优值，第二次利用最优值得到所有的组合。

专心编程………
飞燕算法初级群：3996098
我的Blog

2011-01-02 12:58

StarWing83

来　自：仙女座大星云
等　级：贵宾
威　望：19
帖　子：3951
专家分：748
注　册：2007-11-16

第 18 楼

得分:0

程序代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(void)
{
    struct 
    {
        char *name;
        int size;
        int value;
    } item[] = 
    {
        {"A", 3, 4},
        {"B", 4, 5},
        {"C", 7, 10},
        {"D", 8, 11},
        {"E", 9, 13},
    };
#define ILEN (sizeof(item)/sizeof(item[0]))
#define PSIZE 17

    int max;
    {
        int i, j, v[PSIZE + 1] = {};

        for (i = 0; i < ILEN; ++i)
            for (j = item[i].size; j <= PSIZE; ++j)
                if (v[j] < v[j-item[i].size] + item[i].value)
                    v[j] = v[j-item[i].size] + item[i].value;
        printf("%d\n", max = v[PSIZE]);
    }

    {
        int i, j, v[PSIZE + 1] = {}, s[PSIZE + 1][ILEN] = {};

        for (i = 0; i < ILEN; ++i)
            for (j = item[i].size; j <= PSIZE; ++j)
                if (v[j] <= v[j-item[i].size] + item[i].value)
                {
                    v[j] = v[j-item[i].size] + item[i].value;
                    memcpy(s[j], s[j-item[i].size], sizeof(s[j]));
                    ++s[j][i];

                    if (j == PSIZE && v[j] == max)
                    {
                        int i, j;
                        for (i = 0; i < ILEN; ++i)
                            for (j = 0; j < s[PSIZE][i]; ++j)
                                printf("%s", item[i].name);
                        printf("\n");
                    }
                }
    }

    return 0;
}

[ 本帖最后由 StarWing83 于 2011-1-2 13:05 编辑 ]

专心编程………
飞燕算法初级群：3996098
我的Blog

2011-01-02 12:59

BlueGuy

等　级：版主
威　望：29
帖　子：4476
专家分：4055
注　册：2009-4-18

第 19 楼

得分:0

以下是引用StarWing83在2011-1-2 12:59:38的发言：

#include
#include
#include

int main(void)
{
    struct
    {
        char *name;
        int size;
        int value;
    } item[] =
    {
        {"A", 3, 4},
        {"B", 4, 5},
        {"C", 7, 10},
        {"D", 8, 11},
        {"E", 9, 13},
    };
#define ILEN (sizeof(item)/sizeof(item[0]))
#define PSIZE 17

    int max;
    {
        int i, j, v[PSIZE + 1] = {};

        for (i = 0; i < ILEN; ++i)
            for (j = item.size; j <= PSIZE; ++j)
                if (v[j] < v[j-item.size] + item.value)
                    v[j] = v[j-item.size] + item.value;
        printf("%d\n", max = v[PSIZE]);
    }

    {
        int i, j, v[PSIZE + 1] = {}, s[PSIZE + 1] = {};

        for (i = 0; i < ILEN; ++i)
            for (j = item.size; j <= PSIZE; ++j)
                if (v[j] <= v[j-item.size] + item.value)
                {
                    v[j] = v[j-item.size] + item.value;
                    memcpy(s[j], s[j-item.size], sizeof(s[j]));
                    ++s[j];

                    if (j == PSIZE && v[j] == max)
                    {
                        int i, j;
                        for (i = 0; i < ILEN; ++i)
                            for (j = 0; j < s[PSIZE]; ++j)
                                printf("%s", item.name);
                        printf("\n");
                    }
                }
    }

    return 0;
}

非常好的学习资料啊，

我就是真命天子，顺我者生，逆我者死！

2011-01-02 13:09

古手梨花

等　级：黑侠
威　望：7
帖　子：340
专家分：615
注　册：2010-11-1

第 20 楼

得分:5

n设为一个复数集合，既每个数有两个属性，对应物品的种类和数量，（设n的实数部分为种类值）
把他们的价值设为一个值X,X=n的种类数量值，可有X=n的绝对值，
M为背包容量，M可为n&X的子集，&为某种运算式（是乘法），
因此这个算法有点类似于求一元二次方程的最大值（貌似比这个还简单）。
我不写程序，别喷我

[ 本帖最后由古手梨花于 2011-1-2 13:26 编辑 ]

其实我只会一点“hello world”程序。

2011-01-02 13:24

快速回复：出一个简单的算法题，测测论坛的整体水平