概念

貪心算法（又稱貪婪算法）是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。
對(duì)于背包物品總價(jià)值最大問(wèn)題，簡(jiǎn)單來(lái)說(shuō)，在得知每個(gè)物品的價(jià)格和重量時(shí)，計(jì)算出每個(gè)物品的權(quán)值（價(jià)格除于質(zhì)量），把權(quán)值大的先放到包中，然后根據(jù)權(quán)值大小依次放入。

代碼和解釋

JAVA

先定義一個(gè)物品類

public class Bag {public int weight;//重量public int value;//價(jià)值public double wi;//權(quán)重public String pid;//背包名稱public Bag(int weight, int value, String pid) {this.weight = weight;this.value = value;this.pid = pid;this.wi=(double)value/weight;} }

再定義一個(gè)類，里面定義一個(gè)排序方法，排序方法根據(jù)權(quán)值的大小的每個(gè)物品排序

public class dome {//選擇排序?qū)?shù)組中的bag按權(quán)重排序public static void sort(Bag[] p) {Bag t;for (int i = 0; i < p.length; i++) {int max = i;t = p[i];for (int j = i; j < p.length; j++) {if (t.wi < p[j].wi) {t = p[j];max = j;}}t = p[i];p[i] = p[max];p[max] = t;}}//背包問(wèn)題(貪心算法)public static void bq(Bag[] p, int k, int w, double v) {if (p[k].weight < w) {v = v + p[k].value;System.out.println(p[k].pid + "全部裝入,當(dāng)前背包價(jià)值為" + v);w = w - p[k].weight;bq(p, k + 1, w, v);} else {double a = w * p[k].wi;//當(dāng)前價(jià)值v = v + a;System.out.println(p[k].pid + "裝入了" +((double) w / p[k].weight) + ",當(dāng)前背包價(jià)值為" + v);}} }

最后寫(xiě)一個(gè)main方法測(cè)試

import java.util.Scanner;public class tanxin {public static void main(String[] args) {System.out.println("請(qǐng)輸入背包的容量w和物品的個(gè)數(shù)n:");Scanner scanner = new Scanner(System.in);int w = scanner.nextInt();int n = scanner.nextInt();Bag[] p=new Bag[n];System.out.println("請(qǐng)依次輸入各個(gè)物品的重量w和價(jià)值v和名稱s");int weigth;int value;String pid;for(int i=0;i<n;i++){weigth=scanner.nextInt();value = scanner.nextInt();pid = scanner.next();p[i]=new Bag(weigth,value,pid);}dome.sort(p);dome.bq(p,0,w,0.0);for(int i=0;i<n;i++){System.out.println(p[i].wi+" "+p[i].pid);}} }

運(yùn)行結(jié)果

PYTHON

# 完全背包問(wèn)題，貪心算法 import time class goods:def __init__(self, goods_id, weight=0, value=0):self.id = goods_idself.weight = weightself.value = value # 不適用于0-1背包 def knapsack(capacity=0, goods_set=[]):# 按單位價(jià)值量排序goods_set.sort(key=lambda obj: obj.value / obj.weight, reverse=True)result = []for a_goods in goods_set:if capacity < a_goods.weight:breakresult.append(a_goods)capacity -= a_goods.weightif len(result) < len(goods_set) and capacity != 0:result.append(goods(a_goods.id, capacity, a_goods.value * capacity / a_goods.weight))return result some_goods = [goods(0, 2, 4), goods(1, 8, 6), goods(2, 5, 3), goods(3, 2, 8), goods(4, 1, 2)] start_time = time.clock() res = knapsack(6, some_goods) end_time = time.clock() print('花費(fèi)時(shí)間：' + str(end_time - start_time)) for obj in res:print('物品編號(hào):' + str(obj.id) + ' ,放入重量:' + str(obj.weight) + ',放入的價(jià)值:' + str(obj.value), end=',')print('單位價(jià)值量為:' + str(obj.value / obj.weight))

運(yùn)行結(jié)果

總結(jié)

以上是生活随笔為你收集整理的贪心算法之背包问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。