背包问题

背包问题

问题描述：

　　给定n种物品，1个背包，背包容量为c,每个物品i的价值为v_i，重量为w_i，如何选择装入物品能使背包的总价值最大？

　　注意：与0-1背包问题不同，在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1<=i<=n

形式化描述：

　　给定c >0, w_i >0, v_i >0 , 1≤i≤n.要求找一n元向量A=(x₁,x₂,…,x_n), 0<=x_i<=1【0~1表示取物品的某一部分】,1<=i<=n，使得 ∑ w_ix_i≤c【物品的重量和小于背包总容量】而且∑ v_ix_i达到最大。

算法思路：

　　将物品按照单位重量价值进行排序（从大到小），将尽可能多的单位重量价值最高的物品装入背包，若将这种物品全部装入背包后，背包还有多余容量，则选择单位重量价值次高的并尽可能多地装入背包。如果最后一件物品无法全部装入，则计算可以装入的比例，然后按比例装入。

代码实现：

#include<iostream>
#include<bits/stdc++.h>

using namespace std;
struct item{
    int weight;
    int value;
    float pervalue;
    float rate;
};
bool cmp(const item & a, const item &b  ){
    return a.pervalue<b.pervalue;
}

int main(){
    int n;//n件物品
    float c;//背包容量为c
    cout<<"输入物品件数和背包容量："<<endl;
    cin>>n>>c;
    item * items = new item[n];
    cout<<"依次输入每件物品的价值和重量："<<endl;
    float v[n],w[n];//v[n]：n件物品的价值，w[n]：n件商品的重量
    for(int i=0;i<n;i++){
        cin>>items[i].value>>items[i].weight;
        items[i].pervalue=items[i].value/items[i].weight;//计算单位重量价值
        items[i].rate=0;//初始化每件物品的使用率
    } 
    sort(items,items+n,cmp);
    for (int i = n-1; i >= 0; i--)
    {
        if (c<=0)
            break;
        if (items[i].weight<=c)
        {
            items[i].rate=1;
            c-=items[i].weight;
        }else
        {
            items[i].rate=c/items[i].weight;
            c=0;
        }
    }
    for (int j = n-1; j >= 0; j--)
    {
         cout<<"重："<<items[j].weight<<"  价值："<<items[j].value<<"  被放入了背包"<<endl<<"放入比例："<<items[j].rate<<endl; 
    } 
}