华为OD机试 代表团坐车

题目

某组织举行会议，来了多个代表团同时到达，接待处只有一辆汽车可以同时接待多个代表团，为了提高车辆利用率，请帮接待员计算可以坐满车的接待方案输出方案数量。

约束

1.一个团只能上一辆车，并且代表团人数(代表团数量小于30，每个代表团人数小于30)小于汽车容量(汽车容量小于100)

2.需要将车辆坐满

输入描述

第一行 代表团人数，英文逗号隔开，代表团数量小于30，每个代表团人数小于30第二行 汽车载客量，汽车容量小于100

输出描述

坐满汽车的方案数量

如果无解输出0

示例1:

输入

5,4,2,3,2,4,9

10

输出

4

说明

以下几种方式都可以坐满车，[2,3,5]、[2,4,4]、[2,3,5]、[2,4,4]

动态规划

dp[i][j]的意义:i代表可以选取value数组中0-i编号的元素；j代表客车容纳人数；dpij的值代表i,j限定条件下共有几种方法。

#include <bits/stdc++.h>
using namespace std;


int main() {
    vector<int>value;
    int tmp;
    while (cin >> tmp) {
        value.push_back(tmp);
        if (cin.get() == '\n')
            break;
    }
    sort(value.begin(),value.end());
    int v;
    cin >> v;
    vector<vector<int>>dp(value.size(),vector<int>(v+1,0));
    for (int i = 0; i < value.size(); i++) {
        dp[i][0] = 1;
    }//初始化，第一列初始化为1，原因：空间为0时，不论可选元素范围是多少，只有一种方案-不选取任何元素。
    dp[0][value[0]] = 1;//初始化
    for (int i = 1; i < value.size(); i++) {
        for (int j = 0; j < v + 1; j++) {
            if (j - value[i] >= 0)
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - value[i]];
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    cout << dp[value.size()-1][v];
}

改进：滚动数组降低空间复杂度，注意赋初值和遍历顺序。

#include <bits/stdc++.h>
using namespace std;


int main() {
    vector<int>value;
    int tmp;
    while (cin >> tmp) {
        value.push_back(tmp);
        if (cin.get() == '\n')
            break;
    }
    sort(value.begin(), value.end());
    int v;
    cin >> v;
    vector<int>dp(v + 1, 0);
    dp[0] = 1;
    for (int i = 0; i < value.size(); i++) {
        for (int j=v; j >=0; j--) {
            if(j>=value[i])
                dp[j] = dp[j] + dp[j - value[i]];
           
        }
    }
    cout << dp[v];
}