[数据结构与算法]0-1背包（题解）

本蒟蒻第二次发题解，望多支持。正文如下：

题目描述：

一个旅行者有一个最多能负载m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

输入格式：

第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)； 第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。

输出格式：

仅一行，一个数，表示最大总价值。

样例：

【样例输入】

10 4
2  1
3  3
4  5
7  9

【样例输出】

12

问题分析：

????????旅行者需要在背包能够装下的情况上，装上价值最高的东西。那么如何才能装地最多呢？

? ? ? ? 我们可以选择贪心策略：也就需要考虑到三个贪心的基本问题{

? ? ? ? 1.每次放物品时，将价值最大的物品放入背包中，是否能放下且结果最优？(贪心算法中，一般得到的大多都为最优解的近似解)

? ? ? ? 2.每次放重量最小的物品，能否得到最优解？

? ? ? ? 3.每次选取性价比（价格/重量）最高的物品，能否价值最高？

}

? ? ? ? 我们一一分析：（分析时，要考虑到极端情况）//为方便理解，分析全部使用极端情况

? ? ? ? 1.如果选价值最大的物品，但重量也非常大，那就会出现仅能装下一件物品的情况，肯定是不行的（舍弃）

? ? ? ? 2.如果选择重量最小的物品放入，那价值也不一定高，无法在总重限制的情况下保证价值最大（舍弃）

? ? ? ? 3.每次选择性价比最高的的物品，如果可以达到运载总量（m），那么价值是一定最大的（选用！）

灵感来了！

?算法设计：

????????1：数据结构及初始化：将n种物品存储在结构体内Three（共包含重量、价格、性价比）中，所以我们要将性价比进行排序。运用sum来存储能够带走的最大价值（千千万万，万万千千要初始化为0啊！！！）。

? ? ? ? 2：根据贪心算法，只需要按照从大到小排好性价比,一直达到背包的容量。在选择性价比高的物品后，判断是否小于m，如果小于m，那么我们就将其放入，否则就继续判断，直到结束。

??图解：

伪代码详解：

? ? ? ? （1）数据结构定义：

????????根据算法结构中的结构，先定义结构体Three:

struct Three{

? ? ? ? double w;//每种物品重量

????????double v;//每种物品价值

? ? ? ? double p;//每种物品性价比

}

????????(2)性价比排序：

? ? ? ? ?利用快排函数sort,对性价比进行排序：

sort(begin,end)//参数begin和end表示范围，分别为排序的数组起始地址和尾地址

? ? ? ? ?算法复杂度：

? ? ? ? 时间复杂度：O(nlogn)

? ? ? ? 空间复杂度：O(n)

? ? ? ? 最后附上AC代码?

?

#include<bits/stdc++.h>
using namespace std;
int f[40][210];
int w[40],c[40];
int main() {
	int m,n;
	cin>>m>>n;
	for(int i=1; i<=n; i++) {
		cin>>w[i]>>c[i];
	}
	for(int i=1; i<=n; i++) {
		for(int j=m; j>0; j--) {
			if(w[i]>j) {
				f[i][j]=f[i-1][j];
			} else {
				f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);
			}

		}
	}
	cout<<f[n][m]<<endl;
	return 0;
}

嗯好，赞👍