经典算法详解之背包算法

梦里梦外; 2022-06-13 14:28 192阅读 0赞

** 背包问题**(Knapsackproblem)是一种组合优化的[NP完全问题][NP]。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。这个问题涉及到了两个条件：一是物品总的大小小于或等于背包的大小，二是物品总的价值要尽量大。

如果我们用子问题定义状态来描述的话可以这样解释：

用f\[i\]\[v\]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。用公式表示:

f\[i\]\[v\]=max\{f\[i-1\]\[v\],f\[i-1\]\[v-c\[i\]\]+w\[i\]\}或 f\[v\]=max\{f\[v\],f\[v-c\[i\]\]+w\[i\]\}

具体的解释可以理解为将前i件物品放入容量为v的背包中，现只考虑第i件物品的策略（放或不放），那么就可以转化为一个只涉及前i-1件物品和第i件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f\[i-1\]\[v\]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c\[i\]的背包中”，此时能获得的最大价值就是f\[i-1\]\[v-c\[i\]\]再加上通过放入第i件物品获得的价值w\[i\]。（v表示背包的最大容量，c\[i\]表示第i件物品的大小，w\[i\]表示第i件物品的价值）

算法如下：

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++){//s表示现在背包的大小
 				int p=s-fruits[i].getSize();//表示每次增加单位背包空间，背包所剩的空间
 				int newvalue=value[p]+fruits[i].getPrice();//value[p]表示增加的背包空间可以增加的价值，fruits[i].getprice()表示原有的背包的价值
 				if(newvalue>value[s]){//现有的价值是否大于背包为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]);
 	}
 }

程序运行的过程如下：

i=0时，放入李子

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt; margin-left:.3333in"> 
 <tbody> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> 背包负重 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> s </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> p </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> value </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4500 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4500 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4500 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4500 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 9000 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> item </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 </tr> 
 </tbody> 
</table>

i=1时，放入苹果

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt; margin-left:.3333in"> 
 <tbody> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> 背包负重 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> s </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> p </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> value </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4500 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5700 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5700 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5700 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 9000 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> item </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 </tr> 
 </tbody> 
</table>

i=2时，放入橘子

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt; margin-left:.3333in"> 
 <tbody> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> 背包负重 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> s </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> p </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> value </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2250 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2250 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4500 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5700 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6750 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7950 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 9000 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> item </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 </tr> 
 </tbody> 
</table>

i=3时，放入草莓

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt; margin-left:.3333in"> 
 <tbody> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> 背包负重 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> s </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> p </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> value </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1100 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2250 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3350 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4500 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5700 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6800 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7950 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 9050 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> item </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 </tr> 
 </tbody> 
</table>

i=4时，放入甜瓜

<table style="direction:ltr; border-collapse:collapse; border-style:solid; border-color:#A3A3A3; border-width:1pt; margin-left:.3333in"> 
 <tbody> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> 背包负重 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> s </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 8 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> p </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> － </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> value </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1100 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2250 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3350 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 4500 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 5700 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 6800 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 7950 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 9050 </td> 
 </tr> 
 <tr> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6763in; padding:4pt 4pt 4pt 4pt"> item </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 0 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 1 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.6673in; padding:4pt 4pt 4pt 4pt"> 2 </td> 
 <td style="border-style:solid; border-color:#A3A3A3; border-width:1pt; vertical-align:top; width:.7076in; padding:4pt 4pt 4pt 4pt"> 3 </td> 
 </tr> 
 </tbody> 
</table>

由最后一个表格可以知道，在背包负重8的时候，最多得到价值9050的水果，这个时候可以得到装入的水果是3号水果草莓，那么剩下的（8-1=7）个大小空间，可以知到为2号水果也就是橘子，同理下一步可以知道放入的水果是1号水果苹果。此时获得的最优解的价值就是9050，放入的水果是草莓、橘子和苹果。

到此，我们的背包问题已经解决，要了解上述算法，需要读者分析出背包算法中的每一步都做了什么操作，这一点可以通过上述的表格看出，希望本文对读者理解背包算法有所帮助！

[NP]: http://baike.baidu.com/view/272414.htm