頁:
[1]
一個題目code的觀念解釋
本帖最後由 snowflying 於 2016-5-23 02:13 AM 編輯題目如下:
Independent SET in a path
For a graph G = (V,E), asubSET U of V is an independent SET if there is no edge (v1,v2) forany v1 and v2 in U. Finding the maximum independent SET of a graph is animportant but very difficult problem. However, the problem can be easily solvedwhen the graph is special. Peter is an excellent performer and receives manyinvitations, one for each day. For each performance, he can obtain a pay ofmoney. However, to ensure the qualities, Peter never performs in twoconsecutive days. Please write a program to help Peter to decide whichinvitations he should accept such that the total pay is maximized.This problem is about how to find the maximumweighted independent SET of a path. A path with positive weighted vertices canbe regarded as a one-dimension array. Given an array A ofpositive integers, find an independent SET of its members such that the sum ofthese members is maximum. A SET is independent if no two consecutive members arein the SET. That is, if A[i] in the SET, neither A[i - 1] nor A[i + 1] is in the SET.
[中文]對於圖G = (V,E), 點的子集合U稱為 independent SET 若任兩個U中的點皆無邊相連。計算 maximumindependent SET 是一個重要但困難的問題，不過在某些特殊圖上此問題可以很容易的求解。Peter是一個優秀的表演者，他接到許多的邀約，每天均有一場。每一場表演都可以得到某些金額的報酬，但是為了表演的品質Peter絕對不會連續兩天都進行表演，請你寫一支程式協助他決定應該接受那些表演以得到最大的報酬。這是一個在圖為path時的maximum independent SET問題。我們可將其視為一個正整數的一維陣列，對於所給的正整數陣列A，目標是找一個總和最大的獨立集，在此一個集合被稱為獨立集如果每有任兩個相連的元素被選中，也就是說，若 A[i]在此集合中，則A[i - 1]與A[i + 1]都不在此集合中。
Input: The input consists of several test cases, each in one line. Each case starts froman integer n indicating the number of elements in the array A. Followed this integer there are n positive integers which are A,A,… ,A[n-1]. We suppose that n <=500 and 0 < A[i] <1000. The case with n = 0is the end of the input.Output: Foreach case, output the maximum of the sum of the independent SET of A in oneline.
Sample Input:3 1 2 34 10 9 1 75 5 9 7 2 10
Output of the sample input:41713
我解出來但是寫了很多東西
而我就希望有更短的寫法
上網爬文去找
發現了一個做法
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define N 10001
using namespace std;
int main()
{
int num, i;
while(cin >> num)
{
if(num == 0)
break;
int a, m1, m2, m3;
for(i = 0; i < num; i++)
cin >> a;
m1 = 0;
m3 = m2 = a;
for(i = 1; i < num; i++)
{
m1 = m3;
m2 = m1 + a;
m3 = max(m1, m2);
}
cout << m3 << "\n";
}
return 0;
}
我對幾個陣列的定義有點不明白
希望看懂的大大可以跟我解釋一下感激不盡>"<
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><div></div> 本帖最後由 snowflying 於 2016-5-23 02:55 AM 編輯
如果用 dp + 遞迴 的話，大概長這樣，程式碼也不會太長
#include <cstdio>
#include <cstring>
#include <algorithm>
#define print printf
using namespace std;
int arr;
int dp;
int findMaxSum(int idx, int n)
{
if(idx >= n)
return 0;
if(dp != -1)
return dp;
return dp = max(arr + findMaxSum(idx+2, n), findMaxSum(idx+1, n));
}
int main()
{
int n;
while(scanf("%d", &n) == 1 && n != 0)
{
for(int i = 0 ; i < n ; ++i)
scanf("%d", arr + i);
memset(dp, 0xff, sizeof(dp));
print("%d\n", findMaxSum(0, n));
}
}
這可以寫迴圈版本，而且不需要用到陣列
原本的遞迴式相當於 dp[ i ] = max(arr[ i ] + dp, dp) (邊界自行處理)
而由左往右處理，與由右往左處理，答案不會變
所以可以寫成 dp[ i ] = max(arr[ i ] + dp, dp)
也就是說，只要一直記錄前兩筆就行了
#include <cstdio>
#include <cstring>
#include <algorithm>
#define print printf
using namespace std;
int main()
{
int n, arr, rec, tmp;
while(scanf("%d", &n) == 1 && n != 0)
{
for(int i = 0 ; i < n ; ++i)
scanf("%d", arr + i);
if(n == 1)
{
print("%d\n", arr);
continue;
}
rec = arr;
rec = max(arr, arr);
for(int i = 2 ; i < n ; ++i)
{
tmp = max(arr + rec, rec);
rec = rec;
rec = tmp;
}
print("%d\n", rec);
}
return 0;
}
那份程式碼的概念也差不多是這樣
m1[ i ] 是 m3
m2[ i ] = m1 + a[ i ];
所以 m2[ i ] 是 m3 + a[ i ]
最後 m3[ i ] = max(m1[ i ], m2[ i ]);
即 m3[ i ] = max(m3[ i - 1], m3 + a[ i ])
跟上面的 dp[ i ] = max(arr[ i ] + dp, dp) 一樣的意思
只是這並不需要開到 3 個陣列，而且跑的時候只需要前兩筆的資訊
所以開 3 個變數就行了
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> 本帖最後由 inunu 於 2016-5-23 01:13 PM 編輯
這題的解法概念大概是這樣
從第一個項目開始, 求出各項目的最大積分
直到求出最後一個項目為止
所以你要用迴圈還是遞迴, 老實說只看你自己偏好習慣
我們用 4 10 9 1 7 的例子來講
最前面的 4 只是長度, 略過不看
那我們先說 A[] = {10, 9, 1, 7} 是每個項目本身的分數
S[] 則是每個項目的最大積分
因為 A[] 裡面每個數都 > 0
前三個數你沒有選擇, 一定是
S = A
S = A
S = A + S
從第四個數開始你可以二選一看哪個大:
甲. S = A + S
乙. S = A + S
換句話說:
S = A + max(S, S)
所以用代數 k (k >...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div> inunu 發表於 2016-5-23 01:06 PM static/image/common/back.gif
這題的解法概念大概是這樣
從第一個項目開始, 求出各項目的最大積分
直到求出最後一個項目為止
S = max(A, A);
S = max(A + S, S); 吧
而 S 就已經可以套用遞迴式了 本帖最後由 inunu 於 2016-5-24 05:49 AM 編輯
S 本身並不是二選一的局面
我選擇了分開處理而不是進行檢查
這單純只是個人偏好
沒錯, 我昨天漏講了一個部份就是我的 S 是 "包含了 k 項目" 的最大積分, 必需包含該項目
因此如你所說, 最後答案也必需有兩個選擇, 包含或不包含最後項目
也就是:
甲. S
乙. S
只是提供的 I/O 案例剛好都是前面的情況, 所以昨天也沒注意到
至於我沒辦法用
S = max(A, A);
S = max(A + S, S);
是因為我套用的步進邏輯必需建立在 S 包含 A 的基礎上
#include <stdio.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
int main()
{
int n;
while((scanf("%d", &n) == 1) && (n != 0))
{
int s, s1, s2, s3;
switch(n)
{
case 1:
scanf("%d", &s);
s2 = 0;
break;
case 2:
scanf("%d %d", &s2, &s);
break;
case 3:
scanf("%d %d %d", &s3, &s2, &s);
s += s3;
break;
default:
scanf("%d %d %d", &s3, &s2, &s1);
s1 += s3;
for (n -= 3; n > 0; n--)
{
scanf("%d", &s);
s += MAX(s2, s3);
s3 = s2;
s2 = s1;
s1 = s;
}
}
print f("%d\n", MAX(s, s2));
}
return 0;
}
...<div class='locked'><em>瀏覽完整內容，請先 <a href='member.php?mod=register'>註冊</a> 或 <a href='javascript:;' onclick="lsSubmit()">登入會員</a></em></div><br><br><br><br><br><div></div>
頁:
[1]