※ 引述《DickG (龍龍)》之銘言：
: ※ 引述《alang (別急..深呼吸:))》之銘言：
: : 我跑到第二十組....
: : 還是不行:)
: : 要想想別的方法吧~~
: : 我這題不行....
: alang 是用什麼方法呢?
: 提出來大夥兒討論看看
: 我還沒看這題
: 龍龍
嗯, 那我大概說一下題目好了,
這題大概是說, 給你 n 根長短不一的棍子,
讓你寫一個程式, 想辦法將那些棍子組合成最多根相同長度的棍子,
也就是說長度要最短的意思...
ex.
Input:
9 //九根棍子
5 2 1 5 2 1 5 2 1 //每一根棍子的長度
Output:
6 //5 + 1, 5 + 1, 5 + 1, 2 + 2 + 2
做法大概就是想辦法找出所有的組合, 看看可不可以湊到所需的長度,
像這個 Input 來說, 總和為 24, 我就想辦法去湊總和的因數,
24 的因數有 : 1, 2, 3, 4, 6, 8, 12, 24...
因為最大的數是 5, 所以 1, 2, 3, 4 都不用去跑, 可是可能是
Cut 沒寫好, 程式跑太慢了...:(
大家來討論一下吧!!
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: tp222-251.dialu
> -------------------------------------------------------------------------- <
作者: PwiPwiWorm (小小蟲) 看板: Prob_Solve
標題: Re: ACM 307 Sticks
時間: Fri Jun 18 14:30:22 1999
※ 引述《deathmatch (死亡火柴)》之銘言：
: ※ 引述《DickG (龍龍)》之銘言：
: : alang 是用什麼方法呢?
: : 提出來大夥兒討論看看
: : 我還沒看這題
: : 龍龍
: 嗯, 那我大概說一下題目好了,
: 這題大概是說, 給你 n 根長短不一的棍子,
: 讓你寫一個程式, 想辦法將那些棍子組合成最多根相同長度的棍子,
: 也就是說長度要最短的意思...
: ex.
: Input:
: 9 //九根棍子
: 5 2 1 5 2 1 5 2 1 //每一根棍子的長度
: Output:
: 6 //5 + 1, 5 + 1, 5 + 1, 2 + 2 + 2
: 做法大概就是想辦法找出所有的組合, 看看可不可以湊到所需的長度,
: 像這個 Input 來說, 總和為 24, 我就想辦法去湊總和的因數,
: 24 的因數有 : 1, 2, 3, 4, 6, 8, 12, 24...
: 因為最大的數是 5, 所以 1, 2, 3, 4 都不用去跑, 可是可能是
: Cut 沒寫好, 程式跑太慢了...:(
: 大家來討論一下吧!!
我說說我的想法好了......(我還沒寫下程式)
1.先將資料排序
變成 1 1 1 2 2 2 5 5 5 (放到list裡)
2.找出可能的總合
5 or 5+1 or 5+2
3.test 5
由資料後方scan回來，可先得到三個合為五的值
只要得到合為五的值就delete。於是剩下
1 1 1 2 2 2
下一個得到的是2，不足五，就試著加上下一個值
得到4，還是不足五，就試著加上下一個值
得到6，超過，於是退回一步(合為4)，試著由list前方
加入1，得到合為5。
於是剩下 1 1 2
同樣方法發現合不足五，於是五不能為合
4.test 6
由資料後方scan回來，得到5，不足6，就試著加上下一個值，
得到合為10，超過，於是就退一步，反而從list前方加起
得到合為6。
剩下 1 1 2 2 2 5 5
同理就可以得到4個合為6的值，然後output
我還沒implement成程式，
不知道有沒有比較快?
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: 1.248.rd.ethome
> -------------------------------------------------------------------------- <
作者: smartboy (小光光) 看板: Prob_Solve
標題: Re: ACM 307 Sticks
時間: Sat Jun 19 21:49:22 1999
※ 引述《PwiPwiWorm (小小蟲)》之銘言：
: ※ 引述《smartboy (小光光)》之銘言：
: : 原來那是第幾組呀...
: : 那跑完就不知道了不是嗎? 我是說, 如果當時正好沒看到不就不知道了
: : 另外, 怎麼知道那個就是第幾組呢?
: : 剛沒講的細節, 我用個陣列記錄各長度的個數
: : so, a[51]={0,3,3,0,0,3}
: : sum=24
: : 我從大到小找因數, 先試 12
: : 遞迴第一根, 若第一根湊得出來, 就繼續湊第二根, 若第二根湊出來(12*2)就成功了
: 所以你的答案是12嗎?
: 因為 5+5+2 = 12
: 5+2+2+1+1+1 = 12
: 正確的解不是6?
嗯，很抱歉, 我講錯了, 我是從小到大找因數,
這從我的程式中 for(i=max;i<=sum;i++) 可以看出來
所以前文的順序是錯的. 應該是先找從 6 開始找, 如果找不到再找 12
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: h231.s14.ts30.h
> -------------------------------------------------------------------------- <
作者: smartboy (小光光) 看板: Prob_Solve
標題: Re: ACM 307 Sticks
時間: Sat Jun 19 17:56:01 1999
※ 引述《alang (別急..深呼吸:))》之銘言：
: ※ 引述《smartboy (小光光)》之銘言：
: : 對於每一根的第一個選擇, 我都先選最長的那支棒子
: : (我這方法已不錯了, 還可再改進...)
我所說的可改進是說，在遞迴的順序，
可改成每次取時都比前一次取來得小, 這樣相信可以更快:)
當然這要遞迴時多遞一個參數.
: smartboy
: 可不可以po你的程式上來??
#include <stdio.h>
#include <string.h>
int stick[51];
int max;
int min;
int Count(int size,int empty,int sum)
{
int i;
int flag;
if(sum==0) return 1;
if(empty==0) {
for(i=size<max?size:max ; i>=min ; i--) {
if(stick[i]==0) continue;
stick[i]--;
flag=Count(size,size-i,sum-i);
stick[i]++;
return flag;
break;
}
} else
for(i=empty<max?empty:max ; i>=min ; i--) {
if(stick[i]==0) continue;
stick[i]--;
flag=Count(size,empty-i,sum-i);
stick[i]++;
if(flag) return 1;
}
return 0;
}
int main(void)
{
int i;
int n;
int tmp;
int sum;
while(1) {
scanf("%d",&n);
if(n==0) break;
max=0; sum=0; min=1<<10;
memset(stick,0,51*sizeof(int));
for(i=0;i<n;i++) {
scanf("%d",&tmp);
sum+=tmp;
stick[tmp]++;
if(max<tmp) max=tmp;
if(min>tmp) min=tmp;
}
for(i=max;i<=sum;i++)
if(sum%i==0) {
/* printf("test..%d\n",i);*/
if(Count(i,0,sum)) {
printf("%d\n",i);
break;
}
}
}
return 0;
}
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: oio.m1.ntu.edu.
> -------------------------------------------------------------------------- <
作者: PwiPwiWorm (小小蟲) 看板: Prob_Solve
標題: Re: ACM 307 Sticks
時間: Sat Jun 19 18:52:48 1999
※ 引述《smartboy (小光光)》之銘言：
: ※ 引述《alang (別急..深呼吸:))》之銘言：
在你下面的這一段程式碼
效率不是很好吧!
尤其Count這個function又是很費時間的
如果想一些方法砍掉不合的i值比較能減少時間吧
(
如果遇到棒子數目多，每一根都不長...就會花很多時間
而且題目本身的limit就是數目不限，長度有限....
)
: for(i=max;i<=sum;i++)
: if(sum%i==0) {
: /* printf("test..%d\n",i);*/
: if(Count(i,0,sum)) {
: printf("%d\n",i);
: break;
: }
: }
: }
: return 0;
: }
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: 1.248.rd.ethome