Tag Archives: 背包

LeetCode Shopping Offers

Leave a reply

LeetCode Shopping Offers In LeetCode Store, there are some kinds of items to sell. Each item has a price. However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price. You are given the each item’s price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers. Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer. You could use any of special offers as many times as you want. Example 1: 

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and $5 respectively.
In special offer 1, you can pay $5 for 3A and 0B
In special offer 2, you can pay $10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and $4 for 2A.
Example 2: 
Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and $3 for B, $4 for C.
You may pay $4 for 1A and 1B, and $9 for 2A ,2B and 1C.
You need to buy 1A ,2B and 1C, so you may pay $4 for 1A and 1B (special offer #1), and $3 for 1B, $4 for 1C.
You cannot add more items, though only $9 for 2A ,2B and 1C.
Note:
  1. There are at most 6 kinds of items, 100 special offers.
  2. For each item, you need to buy at most 6 of them.
  3. You are not allowed to buy more items than you want, even if that would lower the overall price.
给定每个商品的单价和需要购买的数量，并且有一些special offer，相当于捆绑销售的优惠套餐。问刚好买到给定数量的商品，所花的最低费用是多少。 注意给定的限制条件中商品最多只有6种，且每件最多只购买6件，所以可以考虑用暴力方法。 把special offer看成一个背包问题里的“商品”，对于每个special offer，我们有两种选择，可以用或者不用。如果需要的needs数组每一项都大于等于某个special offer的每一项，即可以用该special offer，我们比较用和不用该special offer的最终花费，取花费低的。如果用该special offer，则needs数组需要减掉sp捆绑的每件商品的件数，然后继续递归该sp是否可用，相当于完全背包，不计件数的。如果该sp不能用，则递归考虑下一个sp。最后如果递归考虑完所有sp了，则剩余的商品只能按原价购买，算出按原价购买的费用即可。 完整代码如下： [cpp] class Solution { private: int dot(vector<int>& price, vector<int>& needs) { int ans = 0; for (int i = 0; i < needs.size(); ++i) { ans += price[i] * needs[i]; } return ans; } int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) { if (idx == special.size())return dot(price, needs); // 原价购买 int i = 0, n = special[idx].size(); vector<int> small_needs = needs; for (i = 0; i < n – 1; ++i) { if (special[idx][i] > needs[i])break; small_needs[i] -= special[idx][i]; } if (i == n – 1)return min(shopping(price, special, small_needs, idx) + special[idx][n – 1], shopping(price, special, needs, idx + 1)); else return shopping(price, special, needs, idx + 1); } public: int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) { return shopping(price, special, needs, 0); } }; [/cpp] 本代码提交AC，用时6MS。 参考：https://leetcode.com/articles/shopping-offers/，下次记得看到这种数据量非常小的题，首先尝试暴力方法！]]>

LeetCode Combination Sum IV

Leave a reply

LeetCode Combination Sum IV Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target. Example: 

nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?
给定一个数组，问从数组中有放回的取若干个数字，加起来等于target的方案数有多少种。 一开始以为是和LeetCode Combination Sum是类似的，只不过数字可以重复取而已，于是快速写出了如下的DFS版本： [cpp] class Solution { private: void dfs(vector<int>& nums, int sum, int& ans) { if (sum == 0) { ++ans; return; } if (sum < 0)return; for (const auto &i : nums) { if (sum >= i) { dfs(nums, sum – i, ans); } } } public: int combinationSum4(vector<int>& nums, int target) { int ans = 0; dfs(nums, target, ans); return ans; } }; [/cpp] 悲剧的是TLE了，给了一个样例[1,2,3]，target=32，结果有181997601种之多，DFS确实吃不消。 究其原因还是因为每个数可以重复取值，如果每个数最多取一次，也就相当于0/1背包，每个数可以取或者不取，则用DP很好办： [cpp] class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<int> dp(target + 1, 0); dp[0] = 1; for (int i = 0; i < nums.size(); ++i) { // 对每个数字 for (int j = target; j >= nums[i]; –j) { dp[j] += dp[j – nums[i]]; // 取值；不取dp[j]保持不变；所以取和不取加起来就是+=dp[j-nums[i]] } } return dp[target]; } }; [/cpp] 但是这题中，每个数是可以重复取值的。因为数组中的数最小是1，所以每个数最多可以取target次，所以我们可以把0/1背包改成最多取target次的背包问题，也就是对于每个商品，我们可以尝试取1次、2次…target次。 我们可以换一种思路，假设dp[i-1]表示生成和为i-1的所有组合数，那么生成和为i的所有组合数等于所有生成和为i-nums[j]的组合数的和，即所有dp[i-nums[j]]的和。dp[i-nums[j]]表示减去nums[j]此时的组合数。 代码如下： [cpp] class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<int> dp(target + 1, 0); dp[0] = 1; for (int i = 1; i <= target; ++i) { for (int j = 0; j < nums.size(); ++j) { if (i >= nums[j])dp[i] += dp[i – nums[j]]; } } return dp[target]; } }; [/cpp] 本代码提交AC，用时3MS。仔细观察这个版本的代码和上个版本的代码，发现其实就是两层循环换了一下位置，前者求不放回的方案数，后者求放回的方案数。 如果有负数，则要限制每个数的使用次数了，因为如果有数1和-1，要生成和为0的组合数，则可以有无限种，比如[1,-1],[1,1,-1,-1]。]]>

hihoCoder 1506-投掷硬币

Leave a reply

hihoCoder 1506-投掷硬币

#1506 : 投掷硬币

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi有一枚神奇的硬币。已知第i次投掷这枚硬币时，正面向上的概率是Pi。 现在小Hi想知道如果总共投掷N次，其中恰好M次正面向上的概率是多少。

输入

第一行包含两个整数N和M。 第二行包含N个实数P1, P2, … PN。 对于30%的数据，1 <= N <= 20 对于100%的数据，1 <= N <= 1000, 0 <= M <= N, 0 <= Pi <= 1

输出

输出一行一个实数表示恰好M次正面向上的概率。注意行末需要包含一个换行符’\n’。 输出与标准答案误差在0.001以内都被视为正确。
样例输入
2 1
0.5 0.5
样例输出
0.500000
某枚硬币在第i次投掷时，正面向上的概率为Pi，现在投掷N次，问恰好有M次正面向上的概率是多少。 这一题可以看成有N枚硬币，编号1~N，第i枚硬币正面向上的概率为Pi，把所有硬币一起抛向空中，问落地之后出现M枚正面向上的概率。 我一开始是这么做的，每一枚硬币都有可能正面向上或者反面向上，所以枚举所有2^N种情况，累加所有出现M次正面向上的概率。其实就是DFS，代码如下： [cpp] #include<iostream> #include<cstdlib> #include<algorithm> #include<vector> #include<string> #include<unordered_map> using namespace std; double ans = 0; int n, m; void dfs(const vector<double>& probs, double curprob, int step, int up) { if (up == m) { double oneans = curprob; for (int i = step; i < n; ++i)oneans *= (1 – probs[i]); ans += oneans; return; } if (step < n) { dfs(probs, curprob*probs[step], step + 1, up + 1); dfs(probs, curprob*(1 – probs[step]), step + 1, up); } } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); vector<double> probs(n, 0); for (int i = 0; i < n; ++i) scanf("%lf", &probs[i]); dfs(probs, 1, 0, 0); printf("%lf\n", ans); return 0; } [/cpp] 不出所料，本代码提交TLE，只能过30%的数据。 其实每一枚硬币都有正面向上或者反面向上的选择，马上想到背包问题，对于每个商品有选或者不选这两种情况，所以本题实际上也是换了个马甲的背包问题。 令dp[i][j]表示前i枚硬币出现j枚正面向上的概率。那么对于第i枚硬币，有两种选择，如果第i枚硬币正面向上，则前i-1枚硬币只能有j-1枚正面向上，即dp[i][j]+=dp[i-1][j-1]*probs[i]。如果第i枚硬币反面向上，则前i-1枚硬币需要有j枚正面向上，所以dp[i][j-1]+=dp[i-1][j-1]*(1-probs[i])。最终返回dp[n][m]。 代码如下： [cpp] #include<iostream> #include<cstdlib> #include<algorithm> #include<vector> #include<string> #include<unordered_map> using namespace std; int main() { //freopen("input.txt", "r", stdin); int n, m; scanf("%d %d", &n, &m); vector<double> probs(n + 1, 0); for (int i = 1; i <= n; ++i)scanf("%lf", &probs[i]); vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0)); dp[0][0] = 1.0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= i; ++j) { //现在有i枚硬币，所以正面向上的个数j不超过i dp[i][j] += dp[i – 1][j – 1] * probs[i]; // head dp[i][j – 1] += dp[i – 1][j – 1] * (1 – probs[i]); // tail } } printf("%lf\n", dp[n][m]); return 0; } [/cpp] 本代码提交AC，用时48MS。]]>

LeetCode Target Sum

1 Reply

LeetCode Target Sum You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1: 

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
  1. The length of the given array is positive and will not exceed 20.
  2. The sum of elements in the given array will not exceed 1000.
  3. Your output answer is guaranteed to be fitted in a 32-bit integer.
给定一个数组nums，和目标结果S，要求给数组中的每个数加上符号+或-，使得和为S。问共有多少种加符号的方案。 第一反应是DFS，遍历每个数，对其加上+或者-，更新S，然后递归。当遍历完所有数，且和等于0时，找到一种方案。 代码如下： [cpp] class Solution { private: void dfs(vector<int>& nums, int step, int S, int& ans) { if (step == nums.size() && S == 0) { ++ans; return; } if (step == nums.size())return; dfs(nums, step + 1, S – nums[step], ans); dfs(nums, step + 1, S + nums[step], ans); } public: int findTargetSumWays(vector<int>& nums, int S) { int ans = 0; dfs(nums, 0, S, ans); return ans; } }; [/cpp] 本代码提交AC，用时1072MS。居然需要这么长时间，果断优化。 思来想去，这本质是一个背包问题，常规0/1背包是对每个商品要还是不要，这题的背包是，对每个数字，是加正号还是负号。 假设dp[i][j]表示前i个数字之和为j的不同加符号方案数，则有如下递归公式 dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]] 右边第一项是指对第i个数字，要赋加号，那么就要保证前i-1个数字之和是j-nums[i]，这样(j-nums[i])+nums[i]才会等于j。类似的，如果要对第i个数字赋减号，就要保证前i-1个数字之和是j+nums[i]。所以总的就是这两种情况加和。 需要注意的是，因为可以赋负号，所以加和的结果可能是负数（范围是[-sum,sum]），为了dp[i][j]中的j能用下标访问，统一把所有和加上总和sum，做一个偏移（范围是[0,2*sum]），最终结果就是dp[n][S+sum]。 DP的代码如下： [cpp] class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { int n = nums.size(), sum = 0; for (int i = 0; i < n; ++i)sum += nums[i]; if (S<-sum || S>sum)return 0; //if (S == -sum || S == sum)return 1; // nums={1,0},S=1; 1=1+0=1-0 vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 1, 0)); dp[0][sum] = 1; for (int i = 1; i <= n; ++i) { for (int j = 0; j < 2 * sum + 1; ++j) { //考虑第i个数字是+还是- //i从1开始，所以第i个数字的下标是i-1 if (j >= nums[i – 1])dp[i][j] += dp[i – 1][j – nums[i – 1]]; if (j + nums[i – 1] < 2 * sum + 1)dp[i][j] += dp[i – 1][j + nums[i – 1]]; } } return dp[n][S + sum]; } }; [/cpp] 本代码提交AC，用时19MS，加速将近100倍！ DP的问题一般都可以优化空间，比如上述代码可以用两个数组互相滚动赋值来代替n+1个数组。 上面的DP公式理解起来还是有点费劲，下面介绍另一种DP思路，非常简单。 假设我们已经求到前i-1个数字赋不同的符号可以得到的不同和的方案数了，也就是dp[pre]数组，现在要求对第i个数字赋不同符号可能得到的不同和的方案数。那么我们可以遍历dp[pre]数组，只要某个和j对应的方案数不为0（dp[pre][j]!=0），则说明前i-1个数能够组合出和j，且和为j的方案数正好是dp[pre][j]，那么我们只需要在和j的基础上考虑加nums[i]或者减nums[i]，如果对应的j+nums[i]或j-nums[i]没有超出范围，则这一轮和为j+nums[i]的方案数要加上上一轮和为j的方案数，这一轮和为j-nums[i]的方案数要加上上一轮和为j的方案数。 最后返回dp[cur][S+sum]。非常好理解的一个思路。用这种思路还可以求出从给定数组中取任意多个数相加，可以得到的不同和的方案数，其实和这个题类似，只不过把每个数字的状态改为了取和不取。 代码如下： [cpp] class Solution { public: int findTargetSumWays(vector<int>& nums, int S) { int n = nums.size(), sum = 0; for (int i = 0; i < n; ++i)sum += nums[i]; if (S<-sum || S>sum)return 0; vector<vector<int>> dp(2, vector<int>(2 * sum + 1, 0)); int i = 0, pre = (i & 1) ? 1 : 0, cur = (i & 1) ? 0 : 1; dp[pre][sum] = 1; // 取0个数字，加和为0的方案有1种。把和0偏移到sum位置 while (i < n) { pre = (i & 1) ? 1 : 0; cur = (i & 1) ? 0 : 1; for (int j = 0; j < 2 * sum + 1; ++j) { if (dp[pre][j] != 0) { if (j + nums[i] < 2 * sum + 1)dp[cur][j + nums[i]] += dp[pre][j]; // 在j的基础上加nums[i] if (j – nums[i] >= 0)dp[cur][j – nums[i]] += dp[pre][j]; // 在j的基础上减nums[i] } } fill(dp[pre].begin(), dp[pre].end(), 0); // 清空pre数组，因为下一轮pre要用作cur数组 ++i; } return dp[cur][S + sum]; } }; [/cpp] 本代码提交AC，用时13MS。用了两个滚动数组，空间效率高一点。 ]]>

LeetCode Ones and Zeroes

Leave a reply

LeetCode Ones and Zeroes In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue. For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s. Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once. Note:

  1. The given numbers of 0s and 1s will both not exceed 100
  2. The size of given string array won’t exceed 600.
Example 1: 
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
Example 2: 
Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".
给定一个0,1字符串数组，问最多能从中选出多少个字符串，使得所有字符串的’0’和’1’的个数不超过m和n。 明显的背包问题，常规的0/1背包是若干个商品，费用不超过某个值。这里的背包是若干个商品，费用不超过m和n，也就是有两个限制。本题可以用二维背包解决，和一维背包很类似，都是假设某个商品要还是不要，然后更新dp数组。只不过这里有两个限制条件，所以更新数组时需要两个for循环。 一维背包为了优化空间，可以用一维数组，然后从后往前填。二维背包为了优化空间，可以用二维数组，也从后往前填。 假设dp[i][j]表示在i个’0’和j个’1’的限制下，最多能取出的字符串（商品）数，则二维背包代码如下： [cpp] class Solution { public: int findMaxForm(vector<string>& strs, int m, int n) { vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 0; i < strs.size(); ++i) { vector<int> cnts(2, 0); for (int j = 0; j < strs[i].size(); ++j)++cnts[strs[i][j] – ‘0’]; for (int j = m; j >= cnts[0]; –j) { for (int k = n; k >= cnts[1]; –k) { dp[j][k] = max(dp[j][k], dp[j – cnts[0]][k – cnts[1]] + 1); } } } return dp[m][n]; } }; [/cpp] 本代码提交AC，用时66MS。]]>

HDOJ 3535-AreYouBusy

Leave a reply

HDOJ 3535-AreYouBusy AreYouBusy Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3450 Accepted Submission(s): 1342 Problem Description Happy New Term! As having become a junior, xiaoA recognizes that there is not much time for her to AC problems, because there are some other things for her to do, which makes her nearly mad. What’s more, her boss tells her that for some sets of duties, she must choose at least one job to do, but for some sets of things, she can only choose at most one to do, which is meaningless to the boss. And for others, she can do of her will. We just define the things that she can choose as “jobs”. A job takes time , and gives xiaoA some points of happiness (which means that she is always willing to do the jobs).So can you choose the best sets of them to give her the maximum points of happiness and also to be a good junior(which means that she should follow the boss’s advice)? Input There are several test cases, each test case begins with two integers n and T (0<=n,T<=100) , n sets of jobs for you to choose and T minutes for her to do them. Follows are n sets of description, each of which starts with two integers m and s (0<m<=100), there are m jobs in this set , and the set type is s, (0 stands for the sets that should choose at least 1 job to do, 1 for the sets that should choose at most 1 , and 2 for the one you can choose freely).then m pairs of integers ci,gi follows (0<=ci,gi<=100), means the ith job cost ci minutes to finish and gi points of happiness can be gained by finishing it. One job can be done only once. Output One line for each test case contains the maximum points of happiness we can choose from all jobs .if she can’t finish what her boss want, just output -1 . Sample Input 3 3 2 1 2 5 3 8 2 0 1 0 2 1 3 2 4 3 2 1 1 1 3 4 2 1 2 5 3 8 2 0 1 1 2 8 3 2 4 4 2 1 1 1 1 1 1 0 2 1 5 3 2 0 1 0 2 1 2 0 2 2 1 1 2 0 3 2 2 1 2 1 1 5 2 8 3 2 3 8 4 9 5 10 Sample Output 5 13 -1 -1 Author hphp Source 2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU Recommend zhouzeyong | We have carefully selected several similar problems for you: 3033 1712 3449 2639 2159

本题分三种集合，第0种集合内至少要取1个任务；第1种集合内至多取1一个任务；第2种集合内没有任何限制。 集合内部是背包问题，这3种集合之间也是一个背包问题。 假设dp[i][j]表示前i个集合中，耗时为j时取得的最大幸福数量，则： 在第0种集合中，因为至少要取1个任务（耗时c，幸福数g），这个任务可以是本集合的第一个任务dp[i-1][j-c]+g，因为是第一个任务，所以基准是上一个集合i-1；也可以不是第一个任务dp[i][j-c]+g，基准就是本集合i；可以不取这个任务dp[i][j]，所以dp[i][j]=max(dp[i][j], dp[i-1][j-c]+g, dp[i][j-c]+g)，为了至少取一个任务，dp[i][j]必须小于其他2个，所以令dp[i][j]的初始值为-INF。 在第1种集合中，至多取1个任务，都是基于上一个集合，所以不取dp[i-1][j]；取dp[i-1][j-c]+g。 在第2种集合中，是常规0/1背包问题，不取dp[i-1][j]；第一次取dp[i-1][j-c]+g；不是第一次取dp[i][j-c]+g。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; const int kMaxN = 105, kINF = 0x7ffffff; int dp[kMaxN][kMaxN]; int main() { //freopen("input.txt", "r", stdin); int n, t; while (~scanf("%d %d", &n, &t)) { for (int i = 0; i < kMaxN; i++) for (int j = 0; j < kMaxN; j++) dp[i][j] = -kINF; for (int i = 0; i < kMaxN; i++) dp[0][i] = 0; int m, s, c, g; for (int i = 1; i <= n; i++) { scanf("%d %d", &m, &s); if (s == 0) { while (m–) { scanf("%d %d", &c, &g); for (int j = t; j >=c; j–) dp[i][j] = max(dp[i][j], max(dp[i – 1][j – c] + g, dp[i][j – c] + g)); } } else if (s == 1) { for (int j = t; j >= 0; j–) dp[i][j] = dp[i – 1][j]; while (m–) { scanf("%d %d", &c, &g); for (int j = t; j >= c; j–) dp[i][j] = max(dp[i][j], dp[i – 1][j – c] + g); } } else if (s == 2) { for (int j = t; j >= 0; j–) dp[i][j] = dp[i – 1][j]; while (m–) { scanf("%d %d", &c, &g); for (int j = t; j >= c; j–) dp[i][j] = max(dp[i][j], max(dp[i – 1][j – c] + g, dp[i][j – c] + g)); } } } printf("%d\n", max(dp[n][t], -1)); } return 0; } [/cpp] 本代码提交AC，用时31MS，内存1616K。]]>

hihoCoder 1137-Recruitment

Leave a reply

hihoCoder 1137-Recruitment #1137 : Recruitment 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 A company plans to recruit some new employees. There are N candidates (indexed from 1 to N) have taken the recruitment examination. After the examination, the well-estimated ability value as well as the expected salary per year of each candidate is collected by the Human Resource Department. Now the company need to choose their new employees according to these data. To maximize the company’s benefits, some principles should be followed: 1. There should be exactly X males and Y females. 2. The sum of salaries per year of the chosen candidates should not exceed the given budget B. 3. The sum of ability values of the chosen candidates should be maximum, without breaking the previous principles. Based on this, the sum of the salary per year should be minimum. 4. If there are multiple answers, choose the lexicographically smallest one. In other words, you should minimize the smallest index of the chosen candidates; If there are still multiple answers, then minimize the second smallest index; If still multiple answers, then minimize the third smallest one; … Your task is to help the company choose the new employees from those candidates. 输入 The first line contains four integers N, X, Y, and B, separated by a single space. The meanings of all these variables are showed in the description above. 1 <= N <= 100, 0 <= X <= N, 0 <= Y <= N, 1 <= X + Y <= N, 1 <= B <= 1000. Then follows N lines. The i-th line contains the data of the i-th candidate: a character G, and two integers V and S, separated by a single space. G indicates the gender (either “M” for male, or “F” for female), V is the well-estimated ability value and S is the expected salary per year of this candidate. 1 <= V <= 10000, 0 <= S <= 10. We assure that there is always at least one possible answer. 输出 On the first line, output the sum of ability values and the sum of salaries per year of the chosen candidates, separated by a single space. On the second line, output the indexes of the chosen candidates in ascending order, separated by a single space. 样例输入 4 1 1 10 F 2 3 M 7 6 M 3 2 F 9 9 样例输出 9 9 1 2

本题实质上是一个0/1背包问题，将男性和女性分别背包。 以男性为例，转换为从若干个（n1）人中取出X个男性，保证他们的工资总和不超过B，但最大化能力总和。每个应聘者相当于一个物品，工资总和为B相当于容量为B的背包。常规的0/1背包是从这n1个应聘者中挑任意多个，使得工资总和不超过B，但能力总和最大。但是本题的背包限定了取且只取X个应聘者，使得工资总和不超过B，但能力总和最大。 DP的状态转移过程为：假设dpm[i][j]表示从【当前】所有男性中选取i个，工资总和为j时获得的最大能力总和。 假设X=5，当前正好来了5个男性，已经求到了dpm[X][j]，当再来一位男性应聘者a（能力为v，工资为s）时，dpm[X][j]含义就是从当前6位应聘者中选5位满足限定条件。此时有两个选择，要或者不要a，如果不要a，则dpm[X][j]结果不变；如果要a，则前5个只能取4个，加上a就是5个，此时能力总和就是dpm[X-1][j-s]+v，所以最终dpm[X][j]=max{dpm[X][j], dpm[X-1][j-s]+v}。 当把所有男性应聘者都测试过之后，dpm[X][j]就是从所有n1个男性中选X个，其工资总和为j时的能力总和。 最后把男性和女性的情况一组合，再满足总预算不超过B，取全局最优结果。 因为应聘者N最多为100，所以使用数组unsigned long long id[2]来记录应聘者选取情况，unsigned long long 为64位，每位二进制代表一名应聘者，为1选中，id[0]记录前50位，id[1]记录后50位。 完整代码如下： [cpp] #include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int kMaxN = 105, kMaxB = 1005; int dpf[kMaxN][kMaxB], dpm[kMaxN][kMaxB];//dpf[i][j]从所有女性应聘者中选取i个，工资总和为j时的最大能力和 unsigned long long idf[kMaxN][kMaxB][2];//记录女性选取情况 unsigned long long idm[kMaxN][kMaxB][2];//记录男性选取情况 int N, X, Y, B, V, S; char G[2]; int ans_v = 0, ans_s = 0;//总能力，总工资 unsigned long long ans_id[2] = { 0 };//总选取情况 void DP() { dpf[0][0] = dpm[0][0] = 0; int cnt_f = 0, cnt_m = 0, sum_s = 0; for (int i = 1; i <= N; i++) { scanf("%s %d %d", G, &V, &S); sum_s += S; sum_s = min(sum_s, B); if (G[0] == ‘F’) { cnt_f++; cnt_f = min(cnt_f, Y);//最多选取Y位 for (int j = cnt_f; j >= 1; j–) { for (int k = sum_s; k >= S; k–) { if (dpf[j – 1][k – S] < 0) continue; if (dpf[j – 1][k – S] + V > dpf[j][k]) { dpf[j][k] = dpf[j – 1][k – S] + V; idf[j][k][0] = idf[j – 1][k – S][0]; idf[j][k][1] = idf[j – 1][k – S][1]; if (i <= 50) idf[j][k][0] |= 1LL << (i – 1);//选中第i位 else idf[j][k][1] |= 1LL << (i – 1 – 50);//选中第i位 } } } } else { cnt_m++; cnt_m = min(cnt_m, X); for (int j = cnt_m; j >= 1; j–) { for (int k = sum_s; k >= S; k–) { if (dpm[j – 1][k – S] < 0) continue; if (dpm[j – 1][k – S] + V > dpm[j][k]) { dpm[j][k] = dpm[j – 1][k – S] + V; idm[j][k][0] = idm[j – 1][k – S][0]; idm[j][k][1] = idm[j – 1][k – S][1]; if (i <= 50) idm[j][k][0] |= 1LL << (i – 1); else idm[j][k][1] |= 1LL << (i – 1 – 50); } } } } } } void Match() { for (int i = 0; i <= B; i++) { if (dpf[Y][i] == -1) continue; for (int j = 0; j + i <= B; j++) { if (dpm[X][j] == -1) continue; if (dpf[Y][i] + dpm[X][j] > ans_v)//能力更强 { ans_v = dpf[Y][i] + dpm[X][j]; ans_s = i + j; ans_id[0] = idf[Y][i][0] | idm[X][j][0]; ans_id[1] = idf[Y][i][1] | idm[X][j][1]; } else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) < ans_s)//能力相同，但工资更少 { ans_s = i + j; ans_id[0] = idf[Y][i][0] | idm[X][j][0]; ans_id[1] = idf[Y][i][1] | idm[X][j][1]; } else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) == ans_s)//能力和工资都相同 { int id0 = idf[Y][i][0] | idm[X][j][0]; int id1 = idf[Y][i][1] | idm[X][j][1]; if (ans_id[0] > id0)//排序靠前 { ans_id[0] = id0; ans_id[1] = id1; } else if (ans_id[1] > id1)//排序靠前 { ans_id[0] = id0; ans_id[1] = id1; } } } } } void FormatOut() { printf("%d %d\n", ans_v, ans_s); for (int i = 1; i <= 50; i++) { if (ans_id[0] & 1) printf("%d ", i); ans_id[0] >>= 1; } for (int i = 51; i <= 100; i++) { if (ans_id[1] & 1) printf("%d ", i); ans_id[1] >>= 1; } } int main() { memset(dpf, -1, sizeof(dpf)); memset(dpm, -1, sizeof(dpm)); memset(idf, 0, sizeof(idf)); memset(idm, 0, sizeof(idm)); scanf("%d %d %d %d", &N, &X, &Y, &B); DP(); Match(); FormatOut(); return 0; } [/cpp] 代码大部分参考此博客，感谢。 本代码提交AC，用时33MS，内存4MB。]]>

POJ 1837-Balance

1 Reply

POJ 1837-Balance Balance Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 10845 Accepted: 6742 Description Gigel has a strange “balance” and he wants to poise it. Actually, the device is different from any other ordinary balance. It orders two arms of negligible weight and each arm’s length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights. Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced. Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device. It is guaranteed that will exist at least one solution for each test case at the evaluation. Input The input has the following structure: • the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20); • the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: ‘-‘ for the left arm and ‘+’ for the right arm); • on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights’ values. Output The output contains the number M representing the number of possibilities to poise the balance. Sample Input 2 4 -2 3 3 4 5 8 Sample Output 2 Source Romania OI 2002

这一题题意为：给定一个天平，在天平两个臂上有若干个挂钩，给定若干砝码，问将所有砝码都挂上挂钩并使天平平衡的方法数有多少种？这一题有一定的难度，如果只有两个挂钩，问题比较好解决，可以看我的另一篇博客从一个数字序列中取若干个数字使得和为某个数，问共有多少种取数方案；但是这一题的挂钩有若干个，情况比较多，想过用动态规划、背包问题，但是一直想不出状态转换方程。 后来看了某前辈的解题报告，他提出了一个平衡度的概念，并推导出如下的状态转换方程：①dp[i][ j+ w[i]*c[k] ]= ∑(dp[i-1][j])。dp[i][j]表示前i个砝码使平衡度为j共有多少种方案数。 按照常理，我们得到的状态转换方程为：②dp[i][j] =∑(dp[i – 1][j – c[i] * w[i]])，表示dp[i][j]等于前i-1个砝码使平衡度为j-x的方案数之和，这个x就是第i个砝码挂在c个挂钩中的某一个产生的力臂。稍加推导就能得出①等价于②。 有了状态转换方程，我们可以很快的写出代码： [cpp] #include<iostream> using namespace std; int c[21]; int w[21]; int dp[21][15001]; int main() { int n,g; cin>>n>>g; for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=g;i++) cin>>w[i]; dp[0][7500]=1;//不挂任何砝码的时候它本身就平衡了，所以是一种“挂法” for(int i=1;i<=g;i++)//对于每一个砝码 { for(int j=0;j<=15000;j++)//挂上去之后可能使天平出现0-15000中的任意一种状态 { if(dp[i-1][j])//如果这个状态之前出现过，则直接用 { for(int k=1;k<=n;k++) { dp[i][j+w[i]*c[k]]+=dp[i-1][j]; } } } } cout<<dp[g][7500]<<endl; return 0; } [/cpp] 代码提交AC，用时0MS，内存1060K。]]>

hihoCoder 1043-完全背包

Leave a reply

hihoCoder 1043-完全背包 #1043 : 完全背包 时间限制:20000ms 单点时限:1000ms 内存限制:256MB 描述 且说之前的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ 等等，这段故事为何似曾相识？这就要从平行宇宙理论说起了………总而言之，在另一个宇宙中，小Ho面临的问题发生了细微的变化！ 小Ho现在手上有M张奖券，而奖品区有N种奖品，分别标号为1到N，其中第i种奖品需要need(i)张奖券进行兑换，并且可以兑换无数次，为了使得辛苦得到的奖券不白白浪费，小Ho给每件奖品都评了分，其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道，凭借他手上的这些奖券，可以换到哪些奖品，使得这些奖品的喜好值之和能够最大。 提示一： 切，不就是0~1变成了0~K么 提示二：强迫症患者总是会将状态转移方程优化一遍又一遍 提示三：同样不要忘了优化空间哦！ 输入 每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第一行为两个正整数N和M,表示奖品的种数，以及小Ho手中的奖券数。 接下来的n行描述每一行描述一种奖品，其中第i行为两个整数need(i)和value(i)，意义如前文所述。 测试数据保证 对于100%的数据，N的值不超过500，M的值不超过10^5 对于100%的数据，need(i)不超过2*10^5, value(i)不超过10^3 输出 对于每组测试数据，输出一个整数Ans，表示小Ho可以获得的总喜好值。 样例输入 5 1000 144 990 487 436 210 673 567 58 1056 897 样例输出 5940

这一题和之前的0-1背包很类似，只需要稍微修改一下就可以了。 我们先来复习一下之前的0-1背包。0-1背包对于一件物品，要么兑换，要么不兑换，只有两种可能。假设V[i,j]表示用j张奖券兑换前i个物品，则对于第i个物品，我们只有两种选择：1.兑换；2.不兑换。如果不兑换，则V[i,j]=V[i-1,j]，也就是不要第i件物品，用j张奖券兑换前i-1个物品；如果兑换，则V[i,j]=V[i-1,j-need[i]]+value[i]，也就是一定要第i件物品，所以+value[i]，然后再看兑换完第i件物品后剩余的奖券兑换前i-1个物品能得到多少价值。最后就是求这两种情况的最大值。用数学公式表示就是： $$!V[i,j] = \begin{cases}0 & \text{if i=0 or j=0} \\V[i-1,j] & \text{if j < need[i]} \\max \{ V[i-1,j],V[i-1,j-need[i]]+value[i] \} & \text{if i>0 and j$\geq$ need[i]}\\\end{cases}$$ 上面是0-1背包的动态规划状态转换方程，详细的代码可以参考上面的链接。对于完全背包，只需稍微修改即可。 我们首先要理解完全背包的含义，完全背包不限制物品的个数，也就是只要奖券够多，可以兑换多个同一种物品。但是对于某一个物品，也只有两种情况，要么兑换，要么不兑换，不可以将某一件物品拆分成小部分，只兑换其中的0.x。这个地方容易和分数背包混淆。分数背包和0-1类似，每一种物品也只有一个，你可以完整的兑换这一个物品，也可以只兑换这个物品的一部分，但是一种物品只有一个。分数背包可以用贪心算法快速求解，可以参考《算法导论第三版》中文版P243关于0-1背包和分数背包的讨论。 理解了完全背包的含义，我们再来推导其状态转换方程。这个时候对于第i个物品，我们有多种选择：1.不兑换；2.兑换1个；3.多换多个。同样的，我们要从中选一个能使价值最大的方案。如果不兑换，和0-1背包一样，有V[i,j]=V[i-1,j]；但是如果兑换，是不是得一一尝试兑换1个、2个…的所有方案呢？可以这样做，但是还有一个更巧妙的方法，我们先给出公式再解释： $$!V[i,j] = \begin{cases}0 & \text{if i=0 or j=0} \\V[i-1,j] & \text{if j0 and j$\geq$ need[i]}\\\end{cases}$$ 大家仔细对比0-1背包和完全背包的状态转换方程，只改动了一个微小的地方。对于第i个物品，我们如果兑换，则肯定要+value[i]，这是剩下j-need[i]张奖券，因为第i个物品可以兑换多个，所以我们还是用j-need[i]张奖券兑换前i个物品，而不是只兑换前i-1个物品，即V[i,j]=V[i,j-need[i]]+value[i]这样的话，程序自然还会考虑选择第i个物品，也就是兑换多个第i个物品。这就是0-1背包和完全背包的重要区别。 理解了这一点，我们很快就可以写出程序了。代码如下： [cpp] #include <iostream> #include<vector> using namespace std; int main() { int n,m; cin>>n>>m; vector<int> need_vi(n),value_vi(n); for(int i=0;i<n;i++) cin>>need_vi[i]>>value_vi[i]; vector<int> V(m+1,0);//V[j]表示有j张奖券，装前i个奖品获得的最大评分 for(int i=0;i<n;i++)//V[j]表示有j张奖券，装前i个奖品获得的最大评分，每个奖品可以装多个 { for(int j=need_vi[i];j<=m;j++)//从前往后填表，因为这是完全背包 { V[j]=(V[j-need_vi[i]]+value_vi[i]>V[j])?(V[j-need_vi[i]]+value_vi[i]):V[j]; } } cout<<V[m]; return 0; } [/cpp] 具体到写代码时，因为我们正是要利用兑换第i个物品时j=j-need[i]时的值，所以我们从左往右填（从前往后填），这样后面就能利用前面已经修改过的值了。大家可以自己画个表格填一下就知道了，同时请参考联系我之前关于0-1背包的博客。 本代码提交AC，用时148MS，内存0MB。]]>

hihoCoder 1038-01背包

3 Replies

hihoCoder 1038-01背包 #1038 : 01背包 时间限制:20000ms 单点时限:1000ms 内存限制:256MB 描述 且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ 小Ho现在手上有M张奖券，而奖品区有N件奖品，分别标号为1到N，其中第i件奖品需要need(i)张奖券进行兑换，同时也只能兑换一次，为了使得辛苦得到的奖券不白白浪费，小Ho给每件奖品都评了分，其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道，凭借他手上的这些奖券，可以换到哪些奖品，使得这些奖品的喜好值之和能够最大。 提示一：合理抽象问题、定义状态是动态规划最关键的一步 提示二：说过了减少时间消耗，我们再来看看如何减少空间消耗 输入 每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第一行为两个正整数N和M,表示奖品的个数，以及小Ho手中的奖券数。 接下来的n行描述每一行描述一个奖品，其中第i行为两个整数need(i)和value(i)，意义如前文所述。 测试数据保证 对于100%的数据，N的值不超过500，M的值不超过10^5 对于100%的数据，need(i)不超过2*10^5, value(i)不超过10^3 输出 对于每组测试数据，输出一个整数Ans，表示小Ho可以获得的总喜好值。 样例输入 5 1000 144 990 487 436 210 673 567 58 1056 897 样例输出 2099

很简单的0-1背包问题。重新复习一下算法课本P140就好。注意填表的时候，从右往左填，这样只需要一行的空间。如果从左往右填只用一行空间的话，新的数据会覆盖老的数据，但是后面填表的过程中要用到老的数据，所以不行。代码如下： [cpp] #include<iostream> #include<vector> using namespace std; int main() { int n,m; cin>>n>>m; vector<int> need_vi(n);//所需奖券 vector<int> value_vi(n);//评分值 for(int i=0;i<n;i++) cin>>need_vi[i]>>value_vi[i]; vector<int> V(m+1,0);//V[j]表示有j张奖券，装前i个奖品获得的最大评分 for(int i=0;i<n;i++)//V[j]表示有j张奖券，装前i个奖品获得的最大评分 { for(int j=m;j>=need_vi[i];j–)//从后往前填表，能减少空间 { V[j]=(V[j-need_vi[i]]+value_vi[i]>V[j])?(V[j-need_vi[i]]+value_vi[i]):V[j];//要这件奖品和不要的对比 } } cout<<V[m]; return 0; } [/cpp] 代码提交AC，用时148MS，内存0MB。]]>