| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1392 人关注过本帖
标题:来个不好弄的题,谁帮我解答一下啊
只看楼主 加入收藏
吴辉
Rank: 3Rank: 3
来 自:湖南
等 级:论坛游侠
帖 子:52
专家分:199
注 册:2011-3-27
收藏
得分:0 
回复 9楼 b465513006
有道理...这方法是不行。
2011-08-04 20:21
b465513006
Rank: 2
等 级:论坛游民
威 望:1
帖 子:70
专家分:48
注 册:2011-3-18
收藏
得分:0 
但是又枚举不了,数据太大,求哪位高手给个好点的算法,那个,代码顺便给下,我实现代码的能力不是很强
2011-08-04 20:51
piggydog
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2013-1-22
收藏
得分:0 
我试过,这样做可以的:
#include <stdio.h>
#include <string.h>

int main()
{
    int n,m,s,i,j,f[1001],c;
    while(scanf("%d%d%d",&n,&m,&s) == 3)
    {
        memset(f,0,sizeof(f));
        f[0] = 1;
        for(i=0;i<m;i++)
        {
            scanf("%d",&c);
            for(j=s;j>=c;j--)
                if(f[j-c]) //因为现在物品的体积为val[i],你要构成j必需要从 j-val[i]这个积体的状态得到的,如果j-val[i]体积不为真的话就是说j-val[i]体积的状态不存在,不能构成j的状态
                {
                    if(!f[j] && j == c) f[j] = 1;
                    else if(!f[j] || f[j]>f[j-c]+1)//这里f[j]>f[j-c]+1的原因是f[j]是没取第i件物品时取了的物品数;f[j-c]+1是取了第i件物品是的物品总数,取了的价值比没取的大并且件数小,所以是">"
                        f[j] = f[j-c]+1;
                }
        }
        for(i=s;i>=0;i--)
            if(f[i] && f[i]<= n)
            {
                printf("%d\n",i);
                break;
            }
    }
    return 0;
}
2013-01-22 11:50
快速回复:来个不好弄的题,谁帮我解答一下啊
数据加载中...
 
   



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

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