题目描述

给你n个水果，每个水果有一个价值val，还有一个增加的卡路里w，要你求解 $\sum\frac{val_i}{w_i}=k$ 的最大 $\sum val_i$ 。如果无解输出-1。

$1\leq n,val_i,w_i\leq100,1\leq k\leq10$ 。

Solution

我们把式子做个化简即 $\sum val_i=k*\sum w_i$ 。
也就还等于 $\sum val_i-k*\sum w_i=0$ 。这样的前提下求解最大的 $\sum val_i$ ，这个东西是不是在什么地方见过阿，背包的转移式里面。
显然我们可以把 $val_i-k*w_i$ 看成是物品的体积，并且这个体积可能为负数，把 $val_i$ 看成是物品的价值。
我们学过的一般01背包都是正权值，要求是 $\sum w_i=m$ ，这样的前提下求解最大的 $\sum val_i$ 。
那么也就是这题仅仅就是一个可能会带负权值的01背包而已。那么带负权值的01背包怎么处理呢？
那么我们看一般的01背包转移式子。

for (int i = 1; i <= n; ++i)
    for (int j = m; j >= v[i]; --j)
        dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

那么现在 $v[i]$ 是负权值带来的第一个问题就是 $dp$ 数组的下标可能会出现负数，也就是先选一个负数后面加一个整数的样子，所以我们需要把数组下标平移，平移到全部负数都可以由原点减掉一个负数的形式，保证下标不越界。那么处理完下标问题之后，我们接下来的就是最关键 $v_i$ 的取值。

1、如果 $v_i>0$ ，按照正常背包写法即可，注意这个时候的起点要变成偏移量+背包容量。
2、如果 $v_i<0$ ，这个时候我们的写法应该是把容量 $j$ 变成正序的递增了。为什么要变成正序呢，我们想想一般的01背包，为什么要倒叙枚举，就是因为它的转移是来自 $dp[j]=max(dp[j],dp[j-v[i]])$ ，如果你正序递增 $j$ 的话，你当前枚举的这个物品就可能改变了 $dp[j-v[i]]$ 并且延续到后面一次，相当于物品使用无限次，不符合01背包的要求。那么现在看到 $v_i<0$ 的情况，我们转移肯定还是 $dp[j]=max(dp[j],dp[j-v[i]])$ ，这个时候减掉一个负数就变成了加上一个正数了，所以我们要从前面开始往后面推答案，才可以避免多次使用同一件物品。那么实现带负体积的01背包代码就是下面的了。

for (int i = 1; i <= n; ++i) {
        if (v[i] >= 0)
            for (int j = pos + m; j >= v[i]; --j)
                dp[j] = max(dp[j], dp[j - v[i]] + val[i]);
        else
            for (int j = 0; j - v[i] <= pos + m; ++j)
                dp[j] = max(dp[j], dp[j - v[i]] + val[i]);
    }

会了带负权值的01背包之后，这个题目就会变得很简单了，我们上面说的把 $val_i-k*w_i$ 看成体积， $val_i$ 看成价值。求一遍01背包即可。但是这个题目比较特别的一点是它要求 $\sum val_i-\sum k*w_i=0$ ，也就是我们要求到坐标原点的 $dp$ 值就是答案了。

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
#define rep(i, sta, en) for(int i=sta; i<=en; ++i)
#define repp(i, sta, en) for(int i=sta; i>=en; --i)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 100 + 7;

ll n, k;
ll dp[10000007];
ll w[N], val[N];

void solve() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    n = read(), k = read();
    rep(i, 1, n)    val[i] = read();
    rep(i, 1, n)    w[i] = val[i] - k * read();
    int m = 1e5;
    ms(dp, -0x3f);
    dp[m] = 0;
    rep(i, 1, n) {
        if (w[i] >= 0)
            for (int j = 2 * m; j >= w[i]; --j)
                dp[j] = max(dp[j], dp[j - w[i]] + val[i]);
        else
            for (int j = 0; j - w[i] <= 2 * m; ++j)
                dp[j] = max(dp[j], dp[j - w[i]] + val[i]);
    }
    if (!dp[m])    print(-1);
    else print(dp[m]);
}

int main() {
    //int T = read();    while (T--)
    solve();
    return 0;
}

【每日一题】2月5日Dima and Salad 负权值01背包

题目描述

Solution