奇安信多重背包笔试题

原题

有一个人可以洞察市场动向，他能知道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;
}

至此，背包问题完结。