首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
  • 各位大侠进来看看
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-05-16 22:10:28 楼主
    题目:现有1000个球,10个盒子,问各个盒子内应该分别放入多少个球,才能达到需要1至1000
    之间任何数量的球,你都可以用若干盒子组合出来

    我的解法:

    void find()
    {
    int a[10]={0};
    a[0] = 1;
    int index = 0; // 标示已经确定的元素的下标

    for(int i = 2; i <= 1000; ++i)
    {
    bool find = false;
    int sum = 0;
    int b[10] = {0};
    int k = -1;  // 数组b的下标标示,数组b用于存储数组a下标
    int j = 0;
    while (j <= index)
    {
    sum += a[j];
    if (sum == i)
    {
    find = true;
    break;
    }
    else
    {
    if (sum < i)
    {
    if (j == index)  //回溯
    {
    sum -= a[j];
    sum -= a[b[k]];
    j = b[k] + 1;
    --k;
    if (k < -1)
    {
    break;
    }
    }
    else
    {
    b[++k] = j;
    ++j;
    }
    }
    else  // 此处回溯
    {
    sum -= a[j];
    sum -= a[b[k]];
    j = b[k] + 1;
    --k;
    if (k < -1)
    {
    break;
    }
    }
    }
    }
    if (!find)
    {
    a[++index] = i;
    }
    }
    if (i == 1001 && a[9] != 0)
    {
    for (int m = 0; m < 10; ++m)
    {
    cout < < a[m] < < " ";
    }
    }
    else
    {
    cout < <"no Solution ";
    }
    cout < < endl;
    }


    答案好像是出来了,可是发现程序的思路有点混乱,这个程序也是调试了很久才写出来的。我知道这是一般的组合问题,各位大侠能否把这个程序优化下,或者遇到组合问题的时候有什么好的套路没有,免得每次都要写这么长的时间?谢谢!
    50  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-05-16 22:13:471楼 得分:0
    C/C++ code
    void find() { int a[10]={0}; a[0] = 1; int index = 0; // 标示已经确定的元素的下标 for(int i = 2; i <= 1000; ++i) { bool find = false; int sum = 0; int b[10] = {0}; int k = -1; // 数组b的下标标示,数组b用于存储数组a下标 int j = 0; while (j <= index) { sum += a[j]; if (sum == i) { find = true; break; } else { if (sum < i) { if (j == index) //回溯 { sum -= a[j]; sum -= a[b[k]]; j = b[k] + 1; --k; if (k < -1) { break; } } else { b[++k] = j; ++j; } } else // 此处回溯 { sum -= a[j]; sum -= a[b[k]]; j = b[k] + 1; --k; if (k < -1) { break; } } } } if (!find) { a[++index] = i; } } if (i == 1001 && a[9] != 0) { for (int m = 0; m < 10; ++m) { cout << a[m]<< " "; } } else { cout <<"no Solution "; } cout << endl; }


    代码是不是这样贴的?
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • oo
    • 等级:
    发表于:2008-05-16 22:13:572楼 得分:0
    要这么复杂?
    1,2,4,8,..
    2的n次方就行了,最后剩下的不足的话取所有剩下的
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-05-16 22:17:423楼 得分:0
    呵呵!
    这个问题早就回答过了!
    ls的答案!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-05-16 22:45:564楼 得分:0
    oo 怎么想到就是2的n次方的呢?
    还有,针对我的解法,可以做那些优化,一般的组合问题是怎么解决的呢?我写老是要写很长的时间。怎么才能又快又对的写出程序呢?
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-05-17 00:39:125楼 得分:0
    这个就要靠经验了,你多学多做了就自然会了!好好学点东东!一起努力!
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    发表于:2008-05-17 13:02:546楼 得分:0
    引用 2 楼 oo 的回复:
    要这么复杂?
    1,2,4,8,..
    2的n次方就行了,最后剩下的不足的话取所有剩下的


    经典···
    修改 删除 举报 引用 回复

    网站简介广告服务网站地图帮助联系方式诚聘英才English 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved