算法報告(背包)

1、廣義背包問題廣義背包問題的描述如下：給定載重量為 M的背包和n種物品,每種物品有一定的重量和價值， 現(xiàn)在需要設(shè)計算法， 在不超過背包載 重量的前提下，巧妙選擇物品，使得裝入背包的物品的總價值最大化。規(guī)則是，每種物品均可裝入背包多次或不裝入 (但不能僅裝入物品的部分)。在討論廣義背包問題前應(yīng)該先討論最基礎(chǔ)的 01 背包問題。01 背包問題1 題目有N件物品和一個容量為V的背包。放入第i件物品耗費(fèi)的費(fèi)用 是 Wi(weight) ，得到的價值是 Ci(cost) 。求解將哪些物品裝入背包 可使價值總和最大。2 基本思路這是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇 放或不放。用子問題定義

2、狀態(tài)：即 Fi,v 表示前 i 件物品恰放入一個容量 為 v 的背包可以獲得的最大價值。則其狀態(tài)轉(zhuǎn)移方程便是：Fi,v=maxFi - 1,v,Fi- 1,v- Wi+Ci這個方程非常重要， 基本上所有跟背包相關(guān)的問題的方程都是由 它衍生出來的。所以有必要解釋一下： “將前 i 件物品放入容量為 v的背包中”這個子問題，若只考慮第 i 件物品的策略(放或不放) ， 那么就可以轉(zhuǎn)化為一個只和前 i - 1 件物品相關(guān)的問題。 如果不放第 i件物品，那么問題就轉(zhuǎn)化為“前i- 1件物品放入容量為v的背包中”，價值為Fi - 1,v；如果放第i件物品，那么問題就轉(zhuǎn)化為“前i - 1件物品放入剩下的容量

3、為V- Wi的背包中”，此時能獲得的最大價值就是Fi - 1,v- Wi再加上通過放入第i件物品獲得的價值Ci。所以遞歸關(guān)系是:Fi,v=maxFi - 1,v,Fi- 1,v- Wi+Ci(v>=Wi)或 Fi,v=Fi-1,v(0=vvvWi)則容易理解邊界值為：Fi,0=F0,v=0;最優(yōu)解的函數(shù)從遞歸關(guān)系中也能得出Fi,v=Fi-1,v（ 當(dāng)?shù)趇個物品不裝入）Fi,v>Fi-1,v（ 當(dāng)?shù)趇個物品裝入）以上是有關(guān)01背包的討論，現(xiàn)在討論廣義背包的問題。廣義背包問題1問題描述:已知：有一個容量為V的背包和N件物品，第i件物品的重量是weighti，收益是 costi。條件：每

4、種物品都有無限件，能放多少就放多少。問題:在不超過背包容量的情況下，最多能獲得多少價值或收益舉例：物品個數(shù)N二3，背包容量為V = 5，則背包可以裝下的最大價值為40.如下圖:210物品三220物品一物品二3 "價值 52、基本思路（直接擴(kuò)展 01 背包的方程）由于本問題類似于 01背包問題，在 01背包問題中，物品要么取，要么不取，而在完全背包中，物品可以取 0件、取 1件、取 2 件.直到背包放不下位置。因此，可以直接在 01 背包的遞推式中擴(kuò)展得 到：Fiv: 表示前 i 件物品放入容量為 v 的容量中時的最大收益遞推式：Fiv = max(Fi - 1v,Fi - K * w

5、eighti + K *指此時背包容量 ）Valuei); 其中 1 <= K * weighti <= v,(v/ 初始條件f0v = 0;fi0 = 0;Valuei 為第 i 件物品的價值；代碼：#include "stdafx.h"#include <iostream>#include <vector>#include <assert.h>#include <windows.h>#include <stdio.h>#include <windef.h>#include <ios

6、tream>#include <assert.h>using namespace std;/*fiv: 前 i 件物品放入背包容量為 v 的背包獲得的最大收益fiv = max(fi - 1v,fi - 1v - k * Wi + k * Vi,其中 1<=k<= v/Wi)邊界條件f0v = 0;fi0 = 0;*/const int N = 4;/四種物品const int V = 6;/背包的容積為 6int weightN + 1 = 0, 1, 2, 3 ,4;/四種物品的重量分別為 1,2,3,4int ValueN + 1 = 0, 5, 10, 1

7、5,25 ;/四種物品的價值分別為 5,10,20,25int fN + 1V + 1 = 0 ;/fiv初始化為零int Completeknapsack()/ 邊界條件for (int i = 0; i <= N; i+)fi0 = 0;for (int v = 0; v <= V; v+)f0v = 0;/ 遞推for (int i = 1; i <= N; i+)for (int v = 1; v <= V; v+)fiv = 0;int nCount = v / weighti;/背包最多能裝入的同種物品數(shù)量for (int k = 0; k <= nC

8、ount; k+)fiv = max(fiv, fi - 1v - k * weighti+ k * Valuei);/最優(yōu)值函數(shù)int mai n()cout << Comp letek nap sack() << en dl;/輸出system(” pause");/暫停return 1;矩陣圖如下：fiv第i件物品是否裝入，此時容量為v的背包的最大價值4560123000000001051015252530200101520303530001520253040000202530此程序運(yùn)行結(jié)果為35。復(fù)雜度分析：程序需要求解N*V個狀態(tài)，每一個狀態(tài)需要的時間為 O(v/Weighti),所以總的復(fù)雜度為 O(NV*藝(V/Weighti)思考：完全背包問題有一個很簡單有效的優(yōu)化，是這樣的：若