第一题：简单的0/1背包问题
给定N个体积，及容量M，问是否能存在一个选择够成功填满背包。
int main()
{
int N, M;
while (cin >> N >> M) {
int dp[10001];
int weight[1001] = { 0 };
for (int i = 0; i < N; ++i) {
cin >> weight[i];
}
fill(dp, dp + 10001, 6001);
dp[0] = 0;
for (int i = 0; i < N; ++i) {
for (int j = M; j >= weight[i]; --j) {
dp[j] = min(dp[j], dp[j - weight[i]] + 1);
}
}
cout << (dp[M] != 6001 ? "YES" : "NO") << endl;;
}
return 0;
} 第二题：分治+前缀和+记忆化搜索 给定一序列，每次将其分割为两半，和大的扔掉，和小的加入得分
输入： 6
6 2 3 4 5 5
输出：18
6 2 3 4 5 5
输出：18
将问题分解为，对每个可行的区间划分，找到其可能的最大得分；通过构建前缀和数组，快速计算区间和；通过DP数组保存查找过的区间最大得分，防止重复查找。
#include<bits/stdc++.h>
using namespace std;
int dp[501][501] = { 0 };
int Sum[501] = { 0 };
int find_res(vector<int>&data, int l, int r) {
if (l == r - 1)
return 0;
if (dp[l][r] != 0)
return dp[l][r];
int res = 0;
for (int i = l + 1; i < r; ++i) {
int left = Sum[i] - Sum[l];
int right = Sum[r] - Sum[i];
//cout << left << ' ' << right << endl;
if (left < right)
res = max(res, left + find_res(data, l, i));
else if(left > right)
res = max(res, right + find_res(data, i, r));
else {
res = max(res, max(left + find_res(data, l, i), right + find_res(data, i, r)));
}
}
dp[l][r] = res;
return res;
}
int main()
{
int MOD = 1e9 + 7;
int N, M;
cin >> N;
vector<int>data(N);
int save = 0;
for (int i = 0; i < N; ++i) {
cin >> data[i];
save += data[i];
Sum[i + 1] = save;
}
cout << find_res(data, 0, N) << endl;
return 0;
} 
全部评论
(2) 回帖