Timus #1005 – Pancake's Personal Website

题目说明：把全部石头分成两部分，使得两堆石头质量相差最小

题目解析：dp动态规划

因为本人不会/没写过动态规划，该代码实为CSDN上的代码，本人做法为全排列，算法复杂度太高，runtime error。

#include <iostream>
#include <cstdio>
#include <cstring>                  //for memset 
#include <algorithm>                //for max
using namespace std;
const int M = 100;
int w[M];
int dp[M * 100000];
int main()
{
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
        sum += w[i];
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < n; ++i)
        for (int j = sum / 2; j >= w[i]; --j)
            dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
    cout << sum - dp[sum / 2] * 2 << endl;
    return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring> //for memset

#include <algorithm> //for max

using namespace std;

const int M = 100;

int w[M];

int dp[M * 100000];

int main()

{

int n;

cin >> n;

int sum = 0;

for (int i = 0; i < n; ++i) {

cin >> w[i];

sum += w[i];

}

memset(dp, 0, sizeof(dp));

for (int i = 0; i < n; ++i)

for (int j = sum / 2; j >= w[i]; --j)

dp[j] = max(dp[j], dp[j - w[i]] + w[i]);

cout << sum - dp[sum / 2] * 2 << endl;

return 0;

}

发表回复 取消回复

发表回复取消回复