水果沙拉 (salad) hgoi0506

水果沙拉 (salad) hgoi0506 题解


题目描述

  • 有 n 个水果,每个水果有两个属性:美味值和卡路里值。现在选用若干个(至少 1 个)
    水果制作一份特殊的沙拉,沙拉的美味值为所选的水果的美味值的和,沙拉的卡路里值为所
    选水果的卡路里值的和。沙拉的美味值恰好是卡路里值的 K 倍。请计算该沙拉美味值最大
    为多少。

输入

  • 第一行,两个整数 n, k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10);
    第二行,包含 n 个整数,a1, a2, …, an (1 ≤ ai ≤ 100),表示水果的美味值;
    第三行,包含 n 个整数,b1, b2, …, bn (1 ≤ bi ≤ 100),表示水果的卡路里值。
    ##输出
  • 共一行,一个整数,表示最大美味值,若无解则输出-1。

样例

  • 输入样例1
  • 3 2
    10 8 1
    2 7 1
  • 输出样例1
  • 18
  • 输入样例2
  • 5 3
    4 4 4 4 4
    2 2 2 2 2
  • 输出样例2
  • -1

题目解析

  • 一开始看到题目觉得无从下手,能想到的就是用01背包的办法。但单用01背包会造成后效性,即最大值不一定最优的情况
  • 稍加思考,既然最终要达到美味值是卡路里值的k倍,不如以卡路里值的k倍为0,将其数轴左右分成两部分计算
  • 以sp[i]代表第i个物品的美味值 cr[i]代表物品i的卡路里值。
  • 将物品根据sp[i]-k*cr[i]的正负进行分类,装入a,b背包。
  • 以sp[i]-k*cr[i]的绝对值作为重量,sp[i]为价值进行两次01背包。
  • f,g分别代表背包1和背包2的dp数组
  • 当f[i]>0且g[i]>0时,当前i合法即把f[i]+g[i]相加,迭代最大值。
  • 此处的方程与01背包完全相同,使用了滚动数组来节省空间。

附上AC程序
时间复杂度 O (10000*n)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
void finit(){
    freopen("salad.in","r",stdin);
    freopen("salad.out","w",stdout);
}
int n,k;
int sp[101],cr[101],a[101],b[101],ta=0,tb=0,f[10001],g[10001];
int getVal(int t){
    return sp[t]-k*cr[t];
}
int main(){
    finit();
    cin>>n>>k;
    for (int i=1;i<=n;i++)
        cin>>sp[i];
    for (int i=1;i<=n;i++)
        cin>>cr[i];
    int temp;
    for (int i=1;i<=n;i++){
        temp=getVal(i);
        if (temp>=0)
            a[ta++]=i;
        else if (temp<0)
            b[tb++]=i;
    }
    memset(f,0xf3,sizeof(f));
    memset(g,0xf3,sizeof(g));
    f[0]=0;
    g[0]=0;
    for (int i=0;i<ta;i++)
        for (int j=10000;j>=getVal(a[i]);j--)
            f[j]=max(f[j],f[j-getVal(a[i])]+sp[a[i]]);
    for (int i=0;i<tb;i++)
        for (int j=10000;j>=-getVal(b[i]);j--)
            g[j]=max(g[j],g[j+getVal(b[i])]+sp[b[i]]);
    int ss;
    int maxx=-1;
    for (ss=10000;ss>=1;ss--)
        if (f[ss]>0&&g[ss]>0){
            maxx=max(f[ss]+g[ss],maxx);
        }
    cout<<maxx;
    return 0;
}


发表评论

电子邮件地址不会被公开。 必填项已用*标注