动态规划算是一个非常著名的算法，基于此的各类问题也有很多，背包问题也算是赫赫有名，最近看一些OJ机试上都有此类题目。
背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01背包和无限背包，这里主要讨论01背包，即每个物品最多放一个。而无限背包可以转化为01背包。
先说一下算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值。则我们有下面的结果：
（1），v[i][0]=v[0][j]=0;
（2），v[i][j]=v[i-1][j] 当w[i]>j
（3），v[i][j]=max{v[i-1][j],v[i-1][j-w[i]]+v[i]} 当j>=w[i]
好的，我们的算法就是基于此三个结论式得到的递归算法。
下面是Java的具体实现
package sjtuoj;由于需要这是看到一个Online Judge的题目的，因此需要的数据参照ACM数据格式，需要通过Console来输入，依次输入的是 背包的容量，物品数，每个物品的重量和价值。
import java.util.Scanner;
/**
* 0-1背包问题
* 动态规划解决
*
* 令 v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值，则有如下迭代式
* (1) v[i][0]=v[0][j]=0
* (2) v[i][j]=v[i-1][j] wi>j
* (3) v[i][j]=max{v[i-1][j],v[i-1][j-wi]+vi} j>=wi
* */
public class Package01 {
class Item{
public int weight;
public int value;
}
private static int weight,item_num;
private static Item[] item;
/**
* @param n 前n个物品
* @param c 背包容量c
* */
public static int Iterative(int n,int C){
if(n==0 || C==0)
return 0;
else{
for(int i=n-1;i>=0;i--){
if(item[i].weight>C){
return Iterative(n-1,C);
}else{
int temp1=Iterative(n-1,C);
int temp2=Iterative(n-1,C-item[i].weight)+item[i].value;
return temp1>temp2?temp1:temp2;
}
}
}
return 0;
}
public static int getValue(){
int value=0;
return value;
}
public static void main(String[] args){
Scanner s=new Scanner(System.in);
while(s.hasNext()){
weight=s.nextInt();
item_num=s.nextInt();
item=new Item[item_num];
for(int i=0;i<item_num;i++){
item[i]=new Package01().new Item();
item[i].weight=s.nextInt();
item[i].value=s.nextInt();
}
System.out.println(Iterative(item_num,weight));
}
}
}