原题
有一个人可以洞察市场动向,他能知道10天后商品的价格,请问如何分配其本金才能将其收益最大化?
Input:
总计本金:x
商品种类:m
各种类的价格:a, b, c, ...
各种类的限购数量:1, 2, 3, ...
各种类10天后的价格:A, B, C, ...
Output:
这个人10天后的总金
示例:
11
2
6 5
3 2
5 3
输出:
18
1.零一背包
参考这位大佬,强烈建议阅读;
解答:
#include <vector> #include <iostream> #include <string> #include <algorithm> using namespace std; class Stuff { public: Stuff(const initializer_list<int>& li) { auto it = li.begin(); weight = *it++; value = *it; } int weight; int value; int operator<(const Stuff& stuff) { return weight < stuff.weight; } }; std::ostream& operator<<(std::ostream &st, const Stuff& stuff) { st << "(" << stuff.weight << "," << stuff.value << ") "; return st; } int main() { int package_size = 15; vector<Stuff> stuffs({{12,4}, {2,2}, {1,1}, {4,10}, {1,2}}); vector<int> dp(package_size+1); for(int i=0, len=stuffs.size(); i < len; ++i) { for(int j=package_size; j>=stuffs[i].weight; --j) { // 状态转移方程 dp[j] = max(dp[j], dp[j-stuffs[i].weight] + stuffs[i].value); } } for(auto& val : dp) { cout << val << " "; } cout << endl; }
2.完全背包
完全背包(unbounded knapsack problem)与01背包不同就是每种物品可以有无限多个:一共有N种物品,每种物品有无限多个,第i(i从1开始)种物品的重量为w[i],价值为v[i]。在总重量不超过背包承载上限W的情况下,能够装入背包的最大价值是多少?
#include <vector> #include <iostream> #include <string> #include <algorithm> using namespace std; class Stuff { public: Stuff(const initializer_list<int>& li) { auto it = li.begin(); weight = *it++; value = *it; } int weight; int value; int operator<(const Stuff& stuff) { return weight < stuff.weight; } }; std::ostream& operator<<(std::ostream &st, const Stuff& stuff) { st << "(weight=" << stuff.weight << ", value=" << stuff.value << ") "; return st; } int main() { int package_size = 15; vector<Stuff> stuffs({{12,4}, {2,2}, {1,1}, {4,10}, {1,2}}); vector<int> dp(package_size+1); sort(stuffs.begin(), stuffs.end()); for(auto& val : stuffs) cout << val << endl; for(int i=0, len=stuffs.size(); i < len; ++i) { for(int j=stuffs[i].weight; j<=package_size; ++j) { dp[j] = max(dp[j], dp[j-stuffs[i].weight] + stuffs[i].value); } } for(auto& val : dp) { cout << val << " "; } cout << endl; }
这里只修改了for
循环中dp的更新策略,第一层是对于所有物品的遍历,第二层是对所有背包大小的遍历,因为物品不限量,所以物品购买后的状态应该叠加在上一个状态上,因此对j采用了前序遍历的方式。
3.多重背包
多重背包(bounded knapsack problem)与前面不同就是每种物品是有限个:一共有N种物品,第i(i从1开始)种物品的数量为n[i],重量为w[i],价值为v[i]。在总重量不超过背包承载上限W的情况下,能够装入背包的最大价值是多少?
#include <vector> #include <iostream> #include <string> #include <algorithm> using namespace std; class Stuff { public: Stuff(const initializer_list<int>& li) { auto it = li.begin(); weight = *it++; value = *it++; if(it != li.end()) limit=*it; } int weight; int value; int limit = 1; int operator<(const Stuff& stuff) { return weight < stuff.weight; } }; std::ostream& operator<<(std::ostream &st, const Stuff& stuff) { st << "(weight=" << stuff.weight << ", value=" << stuff.value << (stuff.limit <= 1 ? "" : string(", limit=") + to_string(stuff.limit)) << ") "; return st; } int main() { int package_size = 15; vector<Stuff> stuffs({{12, 4, 3}, {2, 2, 6}, {1, 1, 3}, {4, 10, 2}, {1, 2, 2}}); vector<int> dp(package_size+1); sort(stuffs.begin(), stuffs.end()); for(auto& val : stuffs) cout << val << endl; for(int i=0, len=stuffs.size(); i < len; ++i) { const Stuff& s = stuffs[i]; for(int j=package_size; j>=s.weight; --j) { for(int k=1; k<s.limit; ++k){ dp[j] = max(dp[j], dp[j-s.weight] + s.value * k); } } } for(auto& val : dp) { cout << val << " "; } cout << endl; }
至此,背包问题完结。
笔试题解
已知商品的现价为A,10天后的价格为B,则利润value=B-A,限购数量为limit。
已知value, limit, total_price,则可转化为多重背包问题,代入求解即可。