POJ 2184 -- Cow Exhibition (Knapsack)
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(cin.readLine());
s[i] = Integer.parseInt(st.nextToken());
f[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i <= MAX; i++) {
dp[i] = -MAX;
}
dp[ZERO] = 0;
for (int i = 0; i < n; i++) {
if (s[i] < 0) {
for (int c = 0; c - s[i] <= MAX; c++) {
dp[c] = max(dp[c], dp[c - s[i]] + f[i]);
}
} else {
for (int c = MAX; c >= s[i]; c--) {
dp[c] = max(dp[c], dp[c - s[i]] + f[i]);
}
}
}
int max = 0;
for (int c = ZERO; c <= MAX; c++) {
if (dp[c] > 0 && dp[c] + c - ZERO > max) {
max = dp[c] + c - ZERO;
}
}
System.out.println(max);
}Read full article from 2184 -- Cow Exhibition
Description
The cows want to prove to the public that they are both smart and fun. In order to do this, Bessie has organized an exhibition that will be put on by the cows. She has given each of the N (1 <= N <= 100) cows a thorough interview and determined two values for each cow: the smartness Si (-1000 <= Si <= 1000) of the cow and the funness Fi (-1000 <= Fi <= 1000) of the cow.
Bessie must choose which cows she wants to bring to her exhibition. She believes that the total smartness TS of the group is the sum of the Si's and, likewise, the total funness TF of the group is the sum of the Fi's. Bessie wants to maximize the sum of TS and TF, but she also wants both of these values to be non-negative (since she must also show that the cows are well-rounded; a negative TS or TF would ruin this). Help Bessie maximize the sum of TS and TF without letting either of these values become negative.
Bessie must choose which cows she wants to bring to her exhibition. She believes that the total smartness TS of the group is the sum of the Si's and, likewise, the total funness TF of the group is the sum of the Fi's. Bessie wants to maximize the sum of TS and TF, but she also wants both of these values to be non-negative (since she must also show that the cows are well-rounded; a negative TS or TF would ruin this). Help Bessie maximize the sum of TS and TF without letting either of these values become negative.
Input
* Line 1: A single integer N, the number of cows
* Lines 2..N+1: Two space-separated integers Si and Fi, respectively the smartness and funness for each cow.
* Lines 2..N+1: Two space-separated integers Si and Fi, respectively the smartness and funness for each cow.
Output
* Line 1: One integer: the optimal sum of TS and TF such that both TS and TF are non-negative. If no subset of the cows has non-negative TS and non- negative TF, print 0.
Sample Input
5 -5 7 8 -6 6 -3 2 1 -8 -5
Sample Output
8http://blog.sina.com.cn/s/blog_61c7e64d0100kzul.html
牛类想要向世人证明他们聪明又幽默。经过测试，每头牛都有一个幽默度Fi和智商Si，现要求从N头牛中选择
若干头牛去参加比赛，假设这若干头牛的智商之和为sumS,幽默度之和为sumF
现要求在所有选择中，在使得sumS>=0&&sumF>=0的基础上，使得sumS+sumF最大并输出其值.
输入：
第一行：
以下N行：Si
输出：最大的描述中的最大值
若不存在合法的选择，输出0
PS:即选择若干对(si,fi),使得所有的s之和非负，f之和非负，且所有值之和最大
分析：
对于这种一个物品两个属性的问题，即使没有什么体积或者价值那么明显的情况，我们也应该考虑一下01背包是否可行.其实01背包不在于解决什么体积、价值问题，而在于这种动态规划的方法可以记录下来选择某些物品时，得到一个属性的值所对应的时刻另一个属性最优的状态.
那么显然我们就可以通过01背包来得到不同Si的值所对应能得到的Fi的最优值，然后通过枚举所有可能得到的Si值即可比较出最优解.
注意一点就是因为si[i]可能为负，所以范围要扩大一倍.
n = Integer.parseInt(cin.readLine());for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(cin.readLine());
s[i] = Integer.parseInt(st.nextToken());
f[i] = Integer.parseInt(st.nextToken());
}
for (int i = 0; i <= MAX; i++) {
dp[i] = -MAX;
}
dp[ZERO] = 0;
for (int i = 0; i < n; i++) {
if (s[i] < 0) {
for (int c = 0; c - s[i] <= MAX; c++) {
dp[c] = max(dp[c], dp[c - s[i]] + f[i]);
}
} else {
for (int c = MAX; c >= s[i]; c--) {
dp[c] = max(dp[c], dp[c - s[i]] + f[i]);
}
}
}
int max = 0;
for (int c = ZERO; c <= MAX; c++) {
if (dp[c] > 0 && dp[c] + c - ZERO > max) {
max = dp[c] + c - ZERO;
}
}
System.out.println(max);
}Read full article from 2184 -- Cow Exhibition
