Dima and Salad

题目链接：nowcoder 110246

到主站看：https://blog.csdn.net/weixin_43346722/article/details/113792591

题目大意

有一些东西，对于某个东西只能选或不选。每个东西有价值和消耗。

然后要你在保证总价值除以总消耗的值为给定的 k 的情况下，总价值尽可能高。
如果无法弄出，则输出 -1，否则输出最大总价值。

思路

这道题很明显就是 01 背包。

那我们先想想暴力的 01 背包是怎么弄的。
那就是开三维， $f_{i,j,k}$ 表示到第 $i$ 个东西，总价值是 $j$ ，消耗是 $k$ ，这样的状态是否存在。

那你这样空间滚动之后是可以，但是会 TLE。

那你考虑把性质相同的可以弄在一起的状态弄在一起，因为它只是要两个相除是一个数，总有一些状态是相同的。
那我们考虑怎么找。

就从公式找起。
在这里插入图片描述 $a_i,b_i$ 分别表示你你选的物品的价值和消耗组成的数组。

那因为下面如果要一个一个来弄是不可以每次除，那我们移项，是它可以分步处理。
可以化出这个式子： $\sum\limits_{j=1}^{m}a_j-k\times \sum\limits_{j=1}^{m}b_j=0$
那很明显 $\sum\limits_{j=1}^{m}$ 可以放到最外面。 $\sum\limits_{j=1}^{m}(a_j-k\times b_j)=0$

那我们就可以把后面的两维弄成一维，用 $a_i-k\times b_j$ 表示状态。

那原来只是表示这个状态是否存在，那现在我们改成这样，就要看一下题目的要求。题目要总价值尽可能大，那我们就表示的是这个状态能有的最大价值。

然后很明显，状态会有负数，那我们就给它第二维的状态都加一个值使得全都是非负数，就解决了这个问题。

可以用滚动数组来优化空间，但是不优化也可以过，我就懒得优化。

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#define di 20000//因为状态有负数，所以要统一移一下

using namespace std;

int n, k, a[101], b[101];
int c[101], f[101][40001];

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

    for (int i = 1; i <= n; i++)//算出对应的状态值
        c[i] = a[i] - b[i] * k;

    memset(f, -1, sizeof(f));
    f[0][di] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 40000; j >= 0; j--)
            if (f[i - 1][j] != -1) {
                //买
                if (j + c[i] <= 40000 && j + c[i] >= 0)
                 f[i][j + c[i]] = max(f[i][j + c[i]], f[i - 1][j] + a[i]);
                 //不买
                f[i][j] = max(f[i][j], f[i - 1][j]);
            }

    //记得这里第二维不是看 0，而是看移动之后的 “0” 对应的位置
    if (f[n][di]) printf("%d", f[n][di]);
        else printf("-1");

    return 0;
}