| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3739 人关注过本帖
标题:求教这两个01背包问题的动态规划算法 的出来的结果为什么可能不同
只看楼主 加入收藏
qq826647235
Rank: 2
等 级:论坛游民
帖 子:37
专家分:10
注 册:2016-5-4
结帖率:63.64%
收藏
已结贴  问题点数:10 回复次数:4 
求教这两个01背包问题的动态规划算法 的出来的结果为什么可能不同
是一道Hdoj上的01背包问题。
题目如下:
Speakless很早就想出国,现在他已经考完了所有需要的考试,准备了所有要准备的材料,于是,便需要去申请学校了。要申请国外的任何大学,你都要交纳一定的申请费用,这可是很惊人的。Speakless没有多少钱,总共只攒了n万美元。他将在m个学校中选择若干的(当然要在他的经济承受范围内)。每个学校都有不同的申请费用a(万美元),并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”,他大叫一声。帮帮这个可怜的人吧,帮助他计算一下,他可以收到至少一份offer的最大概率。(如果Speakless选择了多个学校,得到任意一个学校的offer都可以)。
 
Input
输入有若干组数据,每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=10000)
后面的m行,每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。
 
Output
每组数据都对应一个输出,表示Speakless可能得到至少一份offer的最大概率。用百分数表示,精确到小数点后一位。



我写了2个程序。。第一个过了,但是我想用时间换空间,就改了一下改成了一维数组。可是题目怎么都过不去了。。为什么

能过的程序
#include<stdio.h>

double Sum[1500][1500];

double Max(double a,double b)
{
    if(a>b) return a;
    else return b;
}

int main()
{
    int n,m;
    int a,i,j;
    int Money[1500];
    double Odds[1500];
    while(1)
    {
        scanf("%d%d",&n,&m);
        if(n==0&&m==0) break;
        for(a=1;a<=m;a++)
        {
            scanf("%d%lf",&Money[a],&Odds[a]);
        }
        for(a=0;a<=n;a++)
        {
            if(a>=Money[1]) Sum[1][a]=Odds[1];
            else  Sum[1][a]=0;
        }

        for(i=2;i<=m;i++)
        {
            for(j=0;j<=n;j++)
            {
                if(j>=Money[i]) Sum[i][j]=Max(Sum[i-1][j],1-(1-Sum[i-1][j-Money[i]])*(1-Odds[i]));
                else Sum[i][j]=Sum[i-1][j];
            }
        }
        printf("%.1lf%%\n",Sum[m][n]*100);
    }
        return 0;
}




不能过的

#include<stdio.h>


double Max(double a,double b)
{
    if(a>b) return a;
    else return b;
}

int main()
{
    int n,m;
    int a,i,j;
    int Money[10001];
    double Sum[10001],Odds[10001];
    while(1)
    {
        scanf("%d%d",&n,&m);
        if(n==0&&m==0) break;
        for(a=1;a<=m;a++)
        {
            scanf("%d%lf",&Money[a],&Odds[a]);
        }
        for(a=0;a<=n;a++)
        {
            if(a>=Money[1]) Sum[a]=Odds[1];
            else  Sum[a]=0;
        }

        for(i=2;i<=m;i++)
        {
            for(j=0;j<=n;j++)
            {
                if(j>=Money[i]) Sum[j]=Max(Sum[j],1-(1-Sum[j-Money[i]])*(1-Odds[i]));

            }

        }
        printf("%.1lf%%\n",Sum[n]*100);
    }
    return 0;
}


我真的看不出来两个程序实际上有什么区别。。求教
搜索更多相关主题的帖子: 背包 大学 学校 
2016-06-03 00:05
qq826647235
Rank: 2
等 级:论坛游民
帖 子:37
专家分:10
注 册:2016-5-4
收藏
得分:0 
只是改了一下改成一维数组就过不了了。。。
2016-06-03 00:06
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
不知道你还在不在,代码没测试,我觉得是这个问题。

背包问题二维转一维有一个关键点就是倒序遍历。

自己查一下看看明不明白我说的什么意思。

ps:不是这个问题的话麻烦给测试数据

[此贴子已经被作者于2016-6-3 10:26编辑过]



[fly]存在即是合理[/fly]
2016-06-03 10:25
qq826647235
Rank: 2
等 级:论坛游民
帖 子:37
专家分:10
注 册:2016-5-4
收藏
得分:0 
回复 3楼 azzbcc
也就是说只要将
  for(j=0;j<=n;j++)
        {
             if(j>=Money[i]) Sum[j]=Max(Sum[j],1-(1-Sum[j-Money[i]])*(1-Odds[i]));

        }
这一段的循环条件改成 for(j=n;j>=Money[i];j- -)
就可以了吗

      
2016-06-05 10:47
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:10 
为什么不先去试一下?


[fly]存在即是合理[/fly]
2016-06-06 17:59
快速回复:求教这两个01背包问题的动态规划算法 的出来的结果为什么可能不同
数据加载中...
 
   



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

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