难度：普及/提高-

题目描述

        LiYuxiang是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子，这个山洞里有一些不同种类的草药，采每一种都需要一些时间，每一种也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
        如果你是LiYuxiang，你能完成这个任务吗？
        此题和原题的不同点:
        1。每种草药可以无限制地疯狂采摘。
        2。药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入输出格式

输入格式:

        输入第一行有两个整数T(1 ≤ T ≤ 100000)和M(1 ≤ M ≤ 10000)，用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到10000之间(包括1和10000)的整数，分别表示采摘某种草药的时间和这种草药的价值。

输出格式:

        输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例

Sample input

70 3
71 100
69 1
1 2

Sample output

140

题解

        无限背包问题，属于经典的线型动态规划。
        与01背包不同的是，无限背包允许每个物品无穷次加入背包。
        设f(x，y)表示在容量剩余y时，将x~m物品加入背包的最大价值。则可列出状态转移方程:

        但是，本题中加大了数据范围，开一个数组int[10000][100000]会造成栈溢出，这里需要压缩数组来将多维数组压至一维。
        根据状态转移方程，易知在二维表中，f(x，y)的值只与其正下方和左方某个值有关，也就是说每个值的求解仅限于相邻两行内。这种情况下可以选择将数组压至一维。根据这个求解顺序，按照从下到上，从左到右的顺序解出每个值。显然只需要开一个int[100000]即可储存当前所需的所有数据。按照这个一维表计算即可。时间复杂度O(n*m)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>

using namespace std;
int t, m;
int value[10001], time0[10001];
int vis[100005] = {0};

int main() {
    cin >> t >> m;
    for (register int i = 1; i <= m; i++)cin >> time0[i] >> value[i];
    for (register int i = 1; i <= t; i++)vis[i] = i / time0[m] * value[m];
    for (register int i = m - 1; i >= 1; i--) {
        for (register int j = 1; j <= t; j++) {
            if (j >= time0[i])vis[j] = max(vis[j - time0[i]] + value[i], vis[j]);
        }
    }
    cout << vis[t];
    return 0;
}