比賽的題目(求解)

kiss94324

裁縫師的困擾
問題描述 : 裁縫師有 N 個工作要完成。並且知道每個工作需要幾個工作天才能完成且一天只能做一個工作。很不幸地，如果工作有延誤的話會有罰金，而且裁縫師也知道每個工作延誤一天所需要的罰金是多少。而延誤天數的計算方式為工作開始的那天往前算到今天（只有第一順位的工作沒有罰金）。  你的目標是撰寫程式來幫助裁縫師找到最低罰金的工作順序。  以第一組 Sample Input 為例：若裁縫師的工作順序為 4 3 2 1 ，那總罰金為： 0*5+5*2+(5+2)*1000+(5+2+1)*4 = 7042 。若順序改為 2 1 3 4 ，則總罰金為： 0*1000+1*4+(1+3)*2+(1+3+2)*5 = 42 。所以採用第二個順序被罰到較少的罰金（同時也是最少的罰金）。  
...

瀏覽完整內容，請先 註冊 或 登入會員

zanelu2011

這裡提供演算法的部份，
程式輸出和輸入的部份，
請自行撰寫。


函式FindBest會列出所有的組合產生的罰款，
請依自己的需求修改。

kmes40505

(大大提供的答案應該是錯得吧...2143比2134付的少...但題意看得懂)
工作天數/罰款:
a   b
c   d
e   f
g   h
...(剩餘項目省略)
假如ab是優先完成項目而cd是第二玩程項目，那罰款式子會是:
d*a + f*(c+a) + h*(e+c+a).....
假如cd是優先完成項目而ab是第二完成項目而剩餘的項目次數不變(剩餘項目可以不變，因為這裡的目的只要比較第一與第二項，後面的項目順序是正確或錯誤並不影響比較，如果還是不理解，假定後面項目是正確的燃後反推試試)，那罰款式子會變成:
...

瀏覽完整內容，請先 註冊 或 登入會員

zanelu2011

kmes40505 發表於 2012-6-22 05:06 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

(大大提供的答案應該是錯得吧...2143比2134付的少...但題意看得懂)
工作天數/罰款:
a   b

工作2134
計算
...

瀏覽完整內容，請先 註冊 或 登入會員

kmes40505

zanelu2011 發表於 2012-6-24 12:12 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

工作2134
計算
0 * 1000 + 1 * 4 + (1+3) * 2 + (1+3+2) * 5 = 42

我猜是對的，但不知道出題的大大怎說

run0006

1. ///////////////////////////////
   
2. class WORK工作
   
3. {
   
4. public:
   
5.    int order;//工作次序 :1~總工作量
   
6.    int cost;//此工作需要天數
   
7.    int forfeit;//罰款
   
8.    int power;//權重
   
9.    int rank;//排名 :1~總工作量
   
10.    WORK(int order1,int cost1,int forfeit1,int power1,int rank1):order(order1),cost(cost1),forfeit
    
11. (forfeit1),power(power1),rank(rank1){}
    
12. };
    
13. //全域變數
    
14. int *sequence; //工作順序
    
15. WORK **work;
    
16. void method(int rank,int order)
    
17. {
    
18. if(work[order]->power >= work[sequence[rank]]->power )
    
19. {
    
20.   method(rank-1,work[sequence[rank]]->order);
    
21.   sequence[rank]=work[order]->order;
    
22. }
    
23. else if(work[order]->power < work[sequence[rank]]->power )
    
24. {
    
25.   method(rank-1,order);
    
26. }
    
27. }
    
28. int main()
    
29. {
    
30. //宣告變數
    
31. 
    
32.     int intthis=0;    int last=0;
    
33. 
    
34.     cin<<取得總工作量.......
    
35. int 總工作量+1=..;
    
36.    
    
37.    //把資料放入WORK work[總工作量]的陣列
    
38.    //初始化變數
    
39.    work=new WORK*[總工作量+1];
    
40. for(int i=1 ; i<總工作量+1 ; i++)
    
41. {
    
42.   sequence=0;
    
43.   work[i]=new WORK(i,..,..,0,總工作量+1);  
    
44. }
    
45.   //程式開始
    
46.   //找出power
    
47.     for(int i=1;i<總工作量+1;i++)
    
48.     {  
    
49.         for(int j=1;j<總工作量+1;j++)
    
50.         {
    
51.             if(i!=j)
    
52.             {
    
53.                 intthis=work[i]->cost*work[j]->forfeit;
    
54.                 if(intthis>last)
    
55.     {
    
56.      last=intthis;
    
57.     }
    
58.              }
    
59.          }
    
60.   work[i]->power=last;
    
61.   last=0;
    
62.     }
    
63. //找出rank
    
64. for(int i=0;i<總工作量+1;i++)
    
65.     {  
    
66.         for(int j=0;j<總工作量+1;j++)
    
67.         {
    
68.    if(i!=j)
    
69.    {
    
70.     if(work[i]->power>work[j].power)
    
71.     {
    
72.      work[i]->rank--;
    
73.     }
    
74.     if(sequence[work[i]->rank]!=0)
    
75.     {
    
76.      sequence[work[i]->rank]=work[i]->order;
    
77.     }
    
78.     else
    
79.     {
    
80.      method(work[i]->rank,work[i]->order);
    
81.      //或者 用method(work[i]->rank,i);
    
82.     }   
    
83.    }
    
84.   }
    
85. }
    
86. return 0;
    
87. }

複製代碼

...

瀏覽完整內容，請先 註冊 或 登入會員

run0006

程式核心應該是排序大小的函式(method)，不是這個問題，簡單講就是要比一串數列的大小。
而問題只是
把別人的罰金 乘上 自己的花費天數得到的power，
power越大代表要越早去完成(順序(rank)越前面)，
了解這一點，
剩下的就是寫程式了。

我的做法是把每一個工作的power找出來，
...

瀏覽完整內容，請先 註冊 或 登入會員

run0006

zanelu2011 發表於 2012-6-24 12:12 PM

下載: 訪客無法瀏覽下載點，請先 註冊 或 登入會員

工作2134
計算
0 * 1000 + 1 * 4 + (1+3) * 2 + (1+3+2) * 5 = 42

同意，理由是 工作1的罰金是3*5=15元，而工作4的罰金是4*4=16元，所以總罰金不會相等。...

瀏覽完整內容，請先 註冊 或 登入會員