部分背包问题

  有n个物品 ，但物品不仅仅只有重量w ,还有价值V，背包的重量上限还是c ， 要使放进背包的物品的重量不超过c的情况下价值总和最大。 【注】物品可以拿一部分并且这部分的重量和价值就按照比例计算。

首先，目标要求价值总和最大，我们很容易想到每次先拿价值最大的。但这样没有考虑到背包的重量这个条件。又因为物品可以按比例取，我们不难想到按照每个物品的“单位重量所含的价值==价值/重量 ”来排序。

然后，我们就按照顺序将单位重量下价值更高的物品整体全部拿走,直到，后来我们的背包所剩余的容量已经不足以放下整个物品了, 那我们就把这最后一个物品拆分只拿走部分,这样我们就填满了背包

(可以注意到此题只要物品总和比背包容量大,背包总是可以被填满)。

#include<iostream>

#include<algorithm>

#define N 100

using namespace std;

struct Node{

int index; //第index件物品

int w;    //物品的重量

int v;   //物品的价值

double cp; //单位重量下物品的价值，为了等会比较是更准确，设置为double型

};

bool cmp(const Node &a,const Node &b){

return a.cp>b.cp;    //根据物体的单位重量的价值由大到小排序

}

int main(){

Node a[N];

int n,c;

cin>>n; //输入初始可选物品总数

cin>>c;//输入背包的容量

for(int i=0;i<n;i++){

cin>>a[i].w;

a[i].index=i+1;

}

for(int i=0;i<n;i++){

cin>>a[i].v;

a[i].cp=(double)a[i].v/a[i].w;

}

sort(a,a+n,cmp); //将所有物品按单位重量的价值递减排序

int number;//number用于统计背包里的物品总个数

double sum=0; //sum用于统计背包里的物品总价值。

for(int i=0;i<n;i++){

   if(c-a[i].w>=0){  //判断背包是否还装的下当前物品

    cout<<"选择单位重量价值为"<<a[i].cp<<"的第"<<a[i].index<<"号物品"<<endl;

    c-=a[i].w;  //将物品放入背包里后背包容量减少。

    sum+=a[i].v;

    number++;

   }

   else{

    printf("选择单位重量价值为%.2f的第%d号物品de一部分\n",a[i].cp,a[i].index);

sum+=(c*a[i].cp);

number++;

break;

   }

}

cout<<"背包里一共装有"<<number<<"件物品"<<endl;

cout<<"背包里的价值总和为"<<sum<<endl;

return 0;

}