算法设计与分析—贪心法求解背包问题C++（学习笔记）

 用贪心法求解如下背包问题的最优解:有7个物品,重量分别为(2,3,5,7,1,4,1)，价值分别为(10,5,15,7,6,18,3),背包容量W=15。写出求解过程。

#include<iostream>
#include <algorithm>
using namespace std;

typedef struct {        //利用结构体联系w和v
	int w;
	int v;
}act;

bool comp(act a, act b) {
	return a.v / a.w > b.v / b.w;              //比较排序
}

int knapsack(act *a, int n, int c) {
	int i;                           //将物品i装入背包
	double x[10] = { 0 };            //物品可部分装入
	int maxvalue = 0;

	for ( i = 0; a[i].w < c; i++) {
		x[i] = 1;
		maxvalue += a[i].v;
		c = c - a[i].w;             //背包容量剩余
	}

	x[i] = (double)c / a[i].w;       //物品i装入一部分
	maxvalue += x[i] * a[i].v;
	return maxvalue;                 //返回背包获得的价值

}

int main() {
	int n;
	cin >> n;
	int c;
	cin >> c;
	act* a = new act[n];

	for (int i = 0; i < n; i++) {
		cin >> a[i].w >> a[i].v;
	}
	
	sort(a, a+n,comp);

	for (int i = 0; i < n; i++) {
		cout << a[i].v << "/" << a[i].w << "得" << a[i].v / a[i].w<<endl;
	 }
	
	int p=knapsack(a, n, c);
	cout <<"最大价值为" << p;

}

 运行截图 ：                                                                

                                                                                                                                       2020.12.5