题1

有n个小朋友,都有属于自己的座位。
请问刚好有一个小朋友坐对座位,但其余都坐错的坐法有几种?

题2

零一背包问题
最气人的就是这个狗比题,之前做过,抄代码都不对,去tmd吧。

#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({{5,2}, {4,2}, {3,3}, {5,5}, {2,1}});
    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;
}

正确答案是16,我算出来11,暂时不知道为啥