头歌实训作业 算法设计与分析-贪心算法(第1关：部分背包问题)

部分背包问题

设有编号为1、2、…、n的n个物品，它们的重量分别为w1、w2、…、wn，价值分别为v1、v2、…、vn，其中wi、vi（1≤i≤n）均为正数。

有一个背包可以携带的最大重量不超过W。求解目标：在不超过背包负重的前提下，使背包装入的总价值最大（即效益最大化），与0/1背包问题的区别是，这里的每个物品可以取一部分装入背包。

编程要求

根据提示，在右侧编辑器补充代码，求解部分背包问题。

测试说明

给定n(n<=100)种物品和一个背包。物品i的重量是wi(wi<=100)，价值为vi(vi<=100)，背包的容量为W(W<=1000)。
应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 

输入：
输入第一行为n和W，分别为物品数量（≤100）和背包容量W（≤1000）。
第二行~第n+1行分别表示每件物品的信息，每行有2个数，分别是物品重量wi(wi<=100)和物品价值vi(vi<=100)。

输出：
输出可以装入背包的物品的最大价值。

样例1：
输入：
3 20
18 25
15 24
10 15

输入解释：3件物品，背包容量为20。
编号为1的物品，重量为18，价值为25。
编号为2的物品，重量为15，价值为24。
编号为3的物品，重量为10，价值为15。

输出：
31.5

输出解释：
装入背包的物品的总价值为31.50。
编号为2的物品整体选择，编号为3的物品选择一半，编号为1的物品不选择。

测试代码 ：

//求解背包问题的算法
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

const double EPS = 1e-6;  //比较精度

//问题表示
int n;
double W;					//限重
struct NodeType
{
	double w;
	double v;
	double p;					//p=v/w
	bool operator<(const NodeType &s) const
	{
		return p > s.p + EPS;			//按p递减排序
	}
};

vector<struct NodeType> a; //物品结点数组

//求解结果表示
double maxv;					// 最大价值
vector<double> x;               // 最优装入方案中各个物品的装入数值
void Knap()						// 求解部分背包问题
{
	/* 请在这里填写答案 */

/**********  Begin  **********/




/**********  End  **********/ 
}

int main()
{
	cin >> n >> W;
    a.resize(n);
    int i;
	for (i = 0; i < n; i++)
		cin >> a[i].w >> a[i].v;
    
    for (i = 0; i < n; i++)			//求v/w
		a[i].p=a[i].v/a[i].w;

	sort(a.begin(), a.end());				//排序

	Knap();

    cout<<maxv<<endl;


	return 0;
}

 补充代码：

//求解背包问题的算法
#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

using namespace std;

const double EPS = 1e-6; //比较精度

//问题表示
int n;
double W; //限重
struct NodeType {
  double w;
  double v;
  double p; //p=v/w
  bool operator < (const NodeType & s) const {
    return p > s.p + EPS; //按p递减排序
  }
};

vector < struct NodeType > a; //物品结点数组

//求解结果表示
double maxv; // 最大价值
vector < double > x; // 最优装入方案中各个物品的装入数值
void Knap() // 求解部分背包问题
{
  /* 请在这里填写答案 */

  /**********  Begin  **********/
  maxv = 0;
  double weight = W;
  for (int i = 0; i < n; i++) {
    if (a[i].w + EPS <= weight) {
      x.push_back(1);
      weight -= a[i].w;
      maxv += a[i].v;

    }
    else if (weight > 0 + EPS) {
      double p = weight / a[i].w;
      x.push_back(p);
      maxv += p * a[i].v;
      weight = 0;
    } else {
      x.push_back(0);
    }
  }

  /**********  End  **********/
}

int main() {
  cin >> n >> W;
  a.resize(n);
  int i;
  for (i = 0; i < n; i++)
    cin >> a[i].w >> a[i].v;

  for (i = 0; i < n; i++) //求v/w
    a[i].p = a[i].v / a[i].w;

  sort(a.begin(), a.end()); //排序

  Knap();

  cout << maxv << endl;

  return 0;
}