题解 | #简单的烦恼#

输入描述:

第一行一个整数 T(T <= 23)，表示数据组数。

在每组输入数据中，第一行有两个正整数，n(n <= 200), t(t <= 80000)，分别表示歌单中歌曲的数目，和题目描述中的t。

第二行中有 n 个正整数 a[i](a[i] <= 400) ，表示每首歌曲的时间长度。

输出描述:

对于每组数据，输出一个 ans，表示最多能听多长时间的歌曲。

示例1

输入

1
3 7
4 3 2

输出

9

说明

先听第2首歌和第3首歌，最后播放第1首歌，在7单位时间后，第3首歌还没有播放完，所以要等第1首歌播放完，共能听9单位时间的歌。

思路

0-1背包问题

先把歌曲的长度由大到小排序；

在不考虑放最后一首歌的情况下，也就是先考略前 n-1 首歌时，在总播放时长不超过 t 的情况下，让前 n-1 首歌的时间尽量长（也就是0-1背包问题），然后再加上最后一首时间最长的歌，得到答案。

所以对前 n-1 首歌进行0-1背包问题一样的处理，得到最长播放时间，最后加上时间最长的歌 v[n] 即可。

AC代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200 + 10, M = 80000 + 10;

int n, t, T;
int f[N][M], v[N];

int main() {
    cin >> T;
    while (T--) {
        cin >> n >> t;
        for (int i = 1; i <= n; i++)  cin >> v[i];
        sort(v + 1, v + 1 + n);
        
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < t; j++) {
                f[i][j] = f[i-1][j];
                if (j - v[i] >= 0) {
                    f[i][j] = max(f[i][j], f[i-1][j-v[i]] + v[i]);
                }
            }
        }
        cout << f[n-1][t-1] + v[n] << endl;
    }
    return 0;
}

链接：https://ac.nowcoder.com/acm/problem/25184
来源：牛客网