吃红薯

[编程题]吃红薯

热度指数：48 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

牛牛参加了大胃王比赛，这次的比赛内容是吃红薯，一共有 $\mathit n$ 根红薯，若已知每根红薯能够提供的饱腹感以及牛牛感到吃撑时的饱腹感需要超过多少，同时，牛牛又非常喜欢吃红薯，那么，在不吃撑的情况下，牛牛最多可以吃多少根红薯？

输入描述:

本题为多组测试数据，第一行输入一个正整数 ，代表测试数据组数。

对于每组测试数据，在第一行输入两个正整数 ，代表美食数量以及牛牛感到吃撑时的饱腹感需要超过 。
第二行输入  个数，依次代表每道美食所能共提供的饱腹感，每道美食能提供的饱腹感不会超过 .

输出描述:

对于每组测试数据，输出一行一个整数代表牛牛在不吃撑的前提下，最多能吃多少根红薯。

示例1

输入

输出

1
0

算法知识视频讲解

Zero′

经典0/1背包

#include<iostream>
#include<cstring>
using namespace std;
const int N = 3010;
int f[N];
int t, n, m;
int main() {
    cin >> t;
    while(t--) {
        memset(f, 0, sizeof f);
        cin >> n >> m;
        for(int i=0;i<n;i++) {
            int x;
            cin >> x;
            for(int j=m;j>=x;j--) f[j] = max(f[j], f[j - x] + 1);
        }
        cout << f[m] << endl;
    }
}

发表于 2022-02-22 15:31:06 回复(0)