部分背包问题虽说是归于背包问题的一种，而且背包问题大多数是通过动态规划的出的结果，但是贪心算法解部分背包，，不管是思想还是操作上来说，都是非常简单的。
首先，我们来看一下什么叫做部分背包。
有N个商品,每个商品的重量为WI,价格为:PI,现有一个背包，最多能装Ｍ的重量． 其中(0<=I< N,0< wi<.M). 问：怎样装能使包中装入的商品价值最高（对于每个商品可以只装该商品的一部分）
那我们就来分析一下条件：： 1. 商品重量不是无限的。
那就说明我们不能只拿一种东西，大多数情况都要进行多个物品的选取。
2. 商品可以被拆分成部分。
那就说明我们需要考虑的不仅是“这个物品能不能装”？，还要考虑“装多少”？在这两种情况下，我们需要考虑的是不能是物品的价值，而是性价比。
3. 商品的属性有两个：重量和价格；
根据这两个属性，我们可以计算出商品的性价比，也就是单价。
4. 要求装入背包中的物品价格最高
那就是说，我们需要按照性价比从高到低的顺序进行，依次装入我们需要得物品，直到背包装满。由于是按照性价比从高到低的顺序进行的选取，那么同样重量的背包，这种方法获得的价值是所有方法中最大的。
所以我们可以大概写出伪代码表示整个求解过程：
sort 先把各个物品按照单价从高到低排序for(循环每一个物品){if(物品的重量小于背包剩余的重量){背包剩余的重量 -= 物品总重量；总价值 += 物品总价值；}else{总价值 += 物品单价*背包剩余重量；退出循环；}}
老规矩，看题 NYOJ 106
背包问题时间限制：3000 ms | 内存限制：65535 KB难度：3
描述 现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,w<=10）；如果给你一个背包它能容纳的重量为m（10<=m<=20）,你所要做的就是把物品装到背包里，使背包里的物品的价值总和最大。
输入 第一行输入一个正整数n（1<=n<=5）,表示有n组测试数据； 随后有n测试数据，每组测试数据的第一行有两个正整数s，m（1<=s<=10）;s表示有s个物品。接下来的s行每行有两个正整数v，w。
输出 输出每组测试数据中背包内的物品的价值和，每次输出占一行。
样例输入 1 3 15 5 10 2 8 3 9
样例输出 65
和之前的分析过程一样，而且这道题直接给的单价，所以更方便，直接上代码：
/*************************************Title: NYOJ 106-背包问题************************************Date：2015/07/23************************************author：刘旭************************************Memory：232KBTime：0ms*************************************/;#define MAX 105struct Node{int w;int v;};Node map[MAX];bool cmp(Node a,Node b){if(a.v != b.v){return a.v > b.v;}return a.w > b.w;}int main(){int T = 0;scanf(“%d”, &T);while(T–){memset(map, -1, sizeof(map));int num = 0;int weight = 0;scanf(“%d%d”, &num, &weight);for(int i = 0; i < num; i++){scanf(“%d%d”, &map[i].v, &map[i].w);}sort(map, map+num, cmp);int ans = 0;for(int i = 0; i < num; i++){if(weight >= map[i].w){weight -= map[i].w;ans += map[i].v * map[i].w;}else{ans += map[i].v * weight;break;}}printf(“%d\n”, ans);}return 0;}
人生最大的错误是不断担心会犯错
