奶牛CJ:有N头奶牛想参加CJ,每头奶牛的智商分别为S_i,情商为F_i。欲挑出一群奶牛使得S之和与F之和都不为负数,且SF之和最大,求此最大值。
01背包
一开学又是工作又是赶寒假作业的,都没时间了( ̄▽ ̄") 。
定义:
dp[i] = j i表示S值之和 + center,j表示F值之和的最大值,center是将坐标原点0往右移动center个单位,保证下标为正的某个值。
这题我只想到了01背包,不知道有没有更高效的算法。S为体积,F为价值。值得思考的是,01背包递推公式dp[j] = max(dp[j], dp[j – S[i]] + F[i]);下标是递减的,如果S是负值的话会导致重复计算,所以此时需要调转循环方向,让下标递增。注意,即使下标递增,它也依然是01背包,不要看着循环方向变了就想当然地认为是完全背包。完全背包的核心不同点是允许同一物品的重复计算,而这里显然没有重复计算!
然后是负值下标的处理,找一个合适的center值就行了,并不需要开那么大的值。
#ifndef ONLINE_JUDGE #pragma warning(disable : 4996) #endif #include <iostream> #include <algorithm> #include <limits> using namespace std; int dp[1000 * 100 * 2 + 16]; // dp[i] = j 当S值之和为i - center时,F值之和j的最大值 int S[100 + 16]; int F[100 + 16]; ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int N; cin >> N; // 真实范围锁定 int center = 1000 * N; // 中心点 int range = center * 2 + 16; // dp数组的利用范围,以center为中心,留了点空隙 for (int i = 0; i < N; ++i) { cin >> S[i] >> F[i]; } // 设定一个很小的值表示这个值无效 memset(dp, 0x80, range * sizeof(int)); // 没有考虑任何奶牛的时候,S之和为0,F值之和为0 dp[center] = 0; // 整个是01背包 for (int i = 0; i < N; ++i) { if (S[i] >= 0) { for (int j = range; j >= S[i]; --j) { dp[j] = max(dp[j], dp[j - S[i]] + F[i]); } } else { // 这不是完全背包,虽然它长得像,但没有发生重复计算 // 所以不是完全背包 for (int j = S[i]; j - S[i] < range; ++j) { dp[j] = max(dp[j], dp[j - S[i]] + F[i]); } } } int result = -range; for (int i = center; i < range; ++i) { if (dp[i] >= 0) { result = max(result, i - center + dp[i]); } } cout << result << endl; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ Cow Exhibition 题解 《挑战程序设计竞赛(第2版)》