部分背包问题

核心算法

    贪心。

问题描述

     

    有 n 件物品，每件重 wi，价值为 vi，且每件物品可以进行分割，
分割后的价值按取走重量占该物品总重量的比值计算。在不超过最大
承载量 C 的范围内，问最大可以取走的价值为多少？

比较

     

    本题在最优装载问题的基础上，增加了价值项，所以不能想最优装载问题先选出较轻的。根据本题的特殊性，我们可以任意地对某一部品进行分割，所以我们优先选择性价比高的物品即可。

    什么是性价比？举个例子，就好比再买菜的时候，对于一样的菜（品种、质量都一样）我们希望买到更便宜的。A店10元3斤，B店7元2斤，那么我们会决定在A店买。这样元和斤都不同的情况下看起来似乎不是很好比较，那我们在计算的时候先计算出单价，也就是每斤的价钱，A店大约3.33元一斤，B店3.5元一斤，这样就可以很轻松的做出选择了。

解题步骤

     

输入

按照题意进行输入

计算

计算每件物品的性价比

排序

把物品按性价比进行排序

（性价比高的排前）

选择

从性价比高的物品开始选择

停止

直到剩余承载力为 0 时停止选择

输出

输出选择商品的总价值

结束

解题步骤

    

//C++

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
struct bag {
    int w,v; //w表示重量 v表示价值
    double p; //用来储存v/w 性价比
}a[10005];
bool cmp(bag x,bag y) {
    return x.p > y.p; //性价比高的物品排在前面
}
int main() {
    int n,c;
    cin>>n>>c; //输入物品件数n和最大承载力t
    for(int i = 0; i < n; i++){
        cin>>a[i].w; //输入n个物品的重量
    }
    for(int i = 0; i < n; i++){
        cin>>a[i].v; //输入n个物品的价值
        a[i].p = (double)a[i].v/a[i].w; //计算每个物品的性价比
    }
    sort(a,a+n,cmp); //对性价比进行排序
    double ans = 0.0;
    for(int i = 0; i < n && t; i++) { //循环条件要附加上c承载力有剩余
        if(c >= a[i].w) { //可以完全选择该物品
            ans += a[i].v; //取走该物品的全部价值
            c -= a[i].w; //承载力减掉物体重量
        }
        else { //剩余承载力不足以取走全部的该物品
            ans += t*a[i].p; //按照性价比进行分割
            c = 0; //承载力无剩余
        }
    }
    printf('%.2f\n', ans); //输出答案
    return 0;
}

注意

    

    在计算性价比的时候要注意一下，在C++中 int/int = int 这样是无法计算出小数的。

题目推荐

     

    有一天,阿里巴巴赶着一头毛驴上山砍柴。砍好柴准备下山时,远处突然出现一股烟尘,弥漫着直向上空飞扬,朝他这儿卷过来,而且越来越近。靠近以后,他才看清原来是一支马队,他们共有四十人,一个个年轻力壮、行动敏捷。一个首领模样的人背负沉重的鞍袋,从丛林中一直来到那个大石头跟前,喃喃地说道:“芝麻,开门吧!”随着那个头目的喊声,大石头前突然出现一道宽阔的门路,于是强盗们鱼贯而入。阿里巴巴待在树上观察他们,直到他们走得无影无踪之后,才从树上下来。他大声喊道:他小心翼翼地走了进去,一下子惊呆了,洞中堆满了财物,还有多得无法计数的金银珠宝,有的散堆在地区上,有的盛在皮袋中。突然看见这么多的金银财富,“芝麻,开门吧!”他的喊声刚落,洞门立刻打开了。阿里巴巴深信这肯定是一个强盗们数代经营、掠夺所积累起来的宝窟。为了让乡亲们开开眼界,见识一下这些宝物,他想一种宝物只拿一个,如果太重就用锤子凿开,但毛驴的运载能力是有限的,怎么才能用驴子运走最大价值的财宝分给穷人呢?阿里巴巴与四十大盗阿里巴巴陷入沉思中......