問題說明:

假設(shè)有一個背包的負(fù)重最多可達(dá)8公斤，而希望在背包中裝入負(fù)重范圍內(nèi)可得之總價物
品，假設(shè)是水果好了，水果的編號、單價與重量如下所示：
0
李子
4KG
NT$4500
1
蘋果
5KG
NT$5700
2
橘子
2KG
NT$2250
3
草莓
1KG
NT$1100
解法背包問題是關(guān)于最佳化的問題，要解最佳化問題可以使用「動態(tài)規(guī)劃」 （Dynamicprogramming） ，從空集合開始，每增加一個元素就先求出該階段的最佳解，直到所有的元素加入至集合中，最后得到的就是最佳解。

下面我們看下代碼:

/* 問題: 假設(shè)有一個背包的負(fù)重最多可達(dá)8公斤，而希望在背包中裝入負(fù)重范圍內(nèi)可得之總價物品 算法說明: 采用動態(tài)規(guī)劃,在當(dāng)前階段求解出最好的解,如此反復(fù) 日期:2013/8/18 張威 */#include <iostream> #include <time.h> using namespace std;#define MAXSIZE 8//定義全局變量 char name[5][5] = {"李子","蘋果","橘子","草莓","甜瓜"};//水果名稱 int wight[5] = {4,5,2,1,6};//單個水果所占斤數(shù) int price[5] = {4500,5700,2250,1100,6700};//單個水果的價值 int perkg_price[5];//每斤水果的價錢 int perkg_num[5] = {0,1,2,3,4};void GetNmae(int num) {for (int i = 0;i <= 4;i++){cout<<name[num][i];} }void GetBestAnswer(int currentwigh) {//判斷遞歸終止條件if (currentwigh >= MAXSIZE){cout<<"包裹已經(jīng)滿了,無法再裝進(jìn)東西"<<endl;}else{//check用來表證到底剩下來的物品里面還有沒有能裝進(jìn)去背包里的bool check = true;int i = 0;for (;i <= 4;i++){//若是沒有進(jìn)入到這個條件內(nèi),說明剩下來的物品的重量都超過了背包剩余重量,到此結(jié)束.否則i就代表當(dāng)前所能選中的最優(yōu)解if (wight[perkg_num[i]] <= MAXSIZE-currentwigh){check = false;break;}}if (check == true){cout<<"已經(jīng)裝不進(jìn)去任何水果了"<<endl;}else{//得到最優(yōu)解,并且將當(dāng)前重量增加,進(jìn)入下一次遞歸currentwigh += wight[perkg_num[i]];cout<<"購買了";GetNmae(perkg_num[i]);cout<<endl;GetBestAnswer(currentwigh);}} }int main() {//計算出每斤水果的價錢,便于動態(tài)規(guī)劃時求出當(dāng)前最佳解for (int i = 0;i <= 4;i++){perkg_price[i] = price[i] / wight[i];}//對perkg_num進(jìn)行排序,同時保證單價和perkg_num之間的一一對應(yīng)關(guān)系.即兩個數(shù)組要同時變化//采用的是冒泡排序,在元素進(jìn)行交換時perkg_num和perkg_price同時變化for (int i = 0;i <= 3;i++){for (int j = i;j <= 3;j++){if (perkg_price[j] < perkg_price[j+1]){int temp1 = perkg_price[j];int temp2 = perkg_num[j];perkg_price[j] = perkg_price[j+1];perkg_price[j+1] = temp1;perkg_num[j] = perkg_num[j+1];perkg_num[j+1] = temp2;}}}//開始計算求解GetBestAnswer(0);return 0; } 背包問題

在這里,算法的主要思想有兩個:1.通過冒泡排序得到一個單價表,并將物品的ID與之配對起來.這樣我們在每次的遞歸中通過ID找到物品的相應(yīng)屬性,篩選出當(dāng)前步驟的最優(yōu)解出來

2.通過遞歸,傳遞當(dāng)前的重量,得到還剩余的重量,根據(jù)前面的單價表,篩選出可選的最優(yōu)解,然后將重量變化進(jìn)入下一次遞歸.

這是最大空間為8的運(yùn)行結(jié)果:????????????????????????????????????????????? 這是最大空間為29的運(yùn)行結(jié)果:

?下面附上指導(dǎo)書上面的代碼:

#include <stdio.h> #include <stdlib.h> #define LIMIT 8 // 重量限制 #define N 5 // 物品種類 #define MIN 1 // 最小重量 struct body { char name[20]; int size; int price; }; 背 包 負(fù) 重 1 2 3 4 5 6 7 8 valu e 110 0 225 0 335 0 450 0 570 0 680 0 795 0 905 0 item 3 2 3 ０ 1 3 2 3 背 包 負(fù) 重 1 2 3 4 5 6 7 8 valu e 110 0 225 0 335 0 450 0 570 0 680 0 795 0 905 0 item 3 2 3 ０ 1 3 2 3 typedef struct body object; int main(void) { int item[LIMIT+1] = {0}; int value[LIMIT+1] = {0}; int newvalue, i, s, p; object a[] = {{"李子", 4, 4500}, {"蘋果", 5, 5700}, {"橘子", 2, 2250}, {"草莓", 1, 1100}, {"甜瓜", 6, 6700}}; for(i = 0; i < N;i++) { for(s = a[i].size; s <= LIMIT;s++) { p = s - a[i].size; newvalue = value[p] + a[i].price; if(newvalue > value[s]) {// 找到階段最佳解 value[s] = newvalue; item[s] = i; } } } printf("物品\t價格\n"); for(i = LIMIT;i >= MIN;i = i - a[item[i]].size) { printf("%s\t%d\n", a[item[i]].name, a[item[i]].price); } printf("合計\t%d\n", value[LIMIT]); return 0; } Java class Fruit { private String name; private int size; private int price; public Fruit(String name,int size, int price){ this.name = name; this.size = size; this.price = price; } public String getName(){ return name; } public int getPrice(){ return price; } public int getSize() { return size; } } public class Knapsack { public static void main(String[] args){ final int MAX = 8; final int MIN = 1; int[] item = new int[MAX+1]; int[] value = new int[MAX+1]; Fruit fruits[] = { new Fruit("李子", 4, 4500), new Fruit("蘋果", 5, 5700), new Fruit("橘子", 2, 2250), new Fruit("草莓", 1, 1100), new Fruit("甜瓜", 6, 6700)}; for(int i = 0; i < fruits.length;i++) { for(int s = fruits[i].getSize(); s <= MAX;s++){ int p = s - fruits[i].getSize(); int newvalue = value[p] + fruits[i].getPrice(); if(newvalue > value[s]) {// 找到階段最佳解 value[s] = newvalue; item[s] = i; } } } System.out.println("物品\t價格"); for(int i = MAX; i >= MIN; i = i - fruits[item[i]].getSize()) { System.out.println(fruits[item[i]].getName()+ "\t" + fruits[item[i]].getPrice()); } System.out.println("合計\t" + value[MAX]); } } 指導(dǎo)書上面的代碼

我居然沒想到使用結(jié)構(gòu)體,失策失策,都沒用什么高級點(diǎn)的數(shù)據(jù)結(jié)構(gòu),看起來貌似很復(fù)雜的樣子.明天再看

轉(zhuǎn)載于:https://www.cnblogs.com/color-my-life/p/3263815.html

總結(jié)

以上是生活随笔為你收集整理的背包问题（Knapsack problem)采用动态规划求解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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