小米OJ #24题 海盗分赃 #27石头收藏家

小米OJ #24题 海盗分赃 #27石头收藏家

• 描述：
  一箱失落多年的宝藏被两位海盗找到，宝箱里的一堆大小与重量各不相同的金块。 他们称出了每个金块的重量，但是如何如何平分这些金子却令他们十分头疼。 程序员们，你能告诉两位海盗，他们能否平分这箱宝藏么？假设宝箱里有三块金子，重量分别为：1,2,3。则他们可以平分这些金子：1+2=3 又假设宝箱里有四块金子，重量分别为：1,2,6,4。则他们无法找到平分的方法。
• 输入：
  一行由逗号分隔的 N 个无序正整数（0<N<100），每个正整数表示每块金子的重量 。W（0<W<10000）。
• 输出：
  字符串true或false，表示海盗们能否平分这些金子。
• 输入样例：

1,2,3
1,2,6,4
1,6,8,3,5,9
10,5,8,6,20,13,7,11

• 输出样例：

true
false
true
true

说明：
1：和小米OJ中的27题石头收藏家解法一摸一样，使用动态规划进行求解。
2：首先如果黄金总重量加起来是奇数，则不管怎么分两个人都不能分一样

if((all_weight)%2) {printf("false");return 0;} 

3：如果所有的黄金重量加起来是偶数，这时候就需要进行动态规划处理：
（1）：如果可以分，肯定是一人一半，所以先拿出一半的黄金重量。这时候假设背包的最大容量max_capacity=一半的黄金重量，只要在题目给定的黄金中，找到一些黄金，把背包填满就行。

（2）：为了方便大家理解，把该问题转化为01背包问题；使得黄金的重量和黄金的价值相等，即1重量的黄金价值也为1，2重量的黄金价值为2，…
（3）：典型的0-1背包问题（和小米OJ27题非常相似）：在给定背包容量的前提下，尽可能装更多价值的黄金。最后判断所计算出来的最大价值是不是等于黄金总重量的一半即可。（注意：黄金的价值和重量相当，计算出来的最大价值也就是最大重量，只要满足总重量的一半，就可以平分。）
（4）：对于此类问题中二维dp数组不好理解的，可以利用0/1背包在线求解网站辅助理解（.html）。
使用测试数据中的第三行：1,6,8,3,5,9

下面给出海盗分赃代码和石头收藏家代码，省的再写一篇了：
海盗分赃

// xiaomiOJ_24.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
#include <iostream>
#include<stdio.h>
#include<string.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
using namespace std;
char gold[10000];
int dp[10000][10000] = { 0 };
int a[100000] = { 0 };
int main()
{int  sum = 0, k = 1;int  num = 0, max_capacity = 0, last_result = 0;gets_s(gold);                                      //读入字符串for (int i = 0; i < strlen(gold); i++) {if (gold[i] == ',') {k++;continue;}else a[k] = a[k] * 10 + gold[i] - '0';}                                             //转换成int数组，放在a中，第一元素置为0。for (int j = 0; j <= k; j++) {sum = sum + a[j];}                                               //求和if (sum % 2) {                        printf("false");return 0;}                                             //奇数判断num = k, max_capacity = sum / 2;for (int i = 1; i <= num; i++) {for (int j = 1; j <= max_capacity; j++) {if (j < a[i]) {dp[i][j] = dp[i - 1][j];}else{dp[i][j] = MAX(dp[i - 1][j], dp[i - 1][j - a[i]] + a[i]);}last_result = MAX(last_result, dp[i][j]);}}                                          //dp结束，后面是判断结果是否为一半if (last_result == (sum / 2)) printf("true");else  printf("false");return 0;
}

程序没优化，将就着看看把~~
石头收藏家

#include <iostream>
#include<stdio.h>
#include<string.h>
#pragma warning(disable:4996)
#define MAX(a,b) (a>b?a:b)
int  last_result = 0;
using namespace std;
int dp[1000][1000] = { 0 };
int main()
{char character;int  a[2][60] = {0}, i = 0, j = 0, num = 0;int max_value = 0, max_capacity = 0;(void)scanf("%d", &max_capacity);while (~scanf("%d%c", &num, &character)) {a[0][++i] = num;if (character == 'n') break;}i = 0;num = 0;while (~scanf("%d%c", &num, &character)) {a[1][++i] = num;if (character == 'n') break;}                                           //需要说明a的第一行存的重量，第二行存的是价值num = i;   //将石头个数也就是数组长度赋给num;//不需要排序，直接使用动态规划进行求解for (int i = 1; i <= num; i++) {for (int j = 1; j <= max_capacity; j++) {if (j < a[0][i]) {dp[i][j] = dp[i - 1][j];}else{dp[i][j] = MAX(dp[i-1][j],dp[i-1][j-a[0][i]]+a[1][i]);}last_result = MAX(last_result, dp[i][j]);}}printf("%d", last_result);return 0;
}

代码通过了就没管了，如有问题欢迎大家指出！