显然这个问题的特点是：每种物品只有一件，可以选择放或者不放。
我主要针对动态规划方法，关于这个问题的文章网上已经相当的多，不过我想把自己的思路和一点想法写下来，也算对这个问题的一点体会吧。
依次考虑N件物品，对于容量为v的背包在处理第i件物品时获得的最大价值F，显然有如下递推式：
IF 第i件物品的费用(体积)C[i]>v
THEN 第i件物品必然无法加入背包，F[i][v]=F[i-1][v]
ELSE是否加入第i件物品需考虑加入背包后是否划算，在这里可以认为这个第i件物品优先加入背包，
那么有 F[i][v]=max{F[i-1][v],F[i-1][v-C[i]]+W[i]}
现在来解释一下上面这个最关键的状态转移方程！
当前背包容量为v，即将处理第i件物品。显然有如下两种方案，出现了最优子结构性质：
a.若第i件物品加入背包，装入这前i件物品获得的最大价值F[i][v]，必然等于第i件物品的价值W[i]再加上向容量为v-C[i]的背包装入前i-1件物品这个子问题的最大价值F[i-1][v-C[i]] (先把第i件物品加入背包，然后考虑安排剩余的空间容量)
b.若不加入第i件物品，装入这前i件物品的获得的最大价值F[i][v]，必然等于向容量为v的背包装入前i-1件物品这个子问题获得的最大价值F[i-1][v]
显然，当前问题的最大价值F[i][v]取上面两种方案的较大值！
代码如下：
import java.util.Scanner;
/**
* 01背包问题
* @author honest
*
*/
public class ZeroOnePack {
public static void main(String[] args) {
int N; //背包数目
int[] weight; //单个物品重量
int[] value; //单个物品价值
int[][] values ; //存放价值
int maxValue; //最大价值
Scanner in=new Scanner(System.in);
maxValue=in.nextInt();
N=in.nextInt();
weight=new int[N+1];
value=new int[N+1];
values=new int[N+1][maxValue+1];
for(int i=1;i<=N;i++){
weight[i]=in.nextInt();
value[i]=in.nextInt();
}
for(int i=0;i<=N;i++)
values[i][0]=0;
for(int i=0;i<=maxValue;i++)
values[0][i]=0;
for ( int i = 1; i <= N; i++){
for ( int j = 1; j<=maxValue; j++){
if(weight[i]>
j){
values[i][j]=values[i-1][j];
}else {
values[i][j]=Math.max(values[i-1][j-weight[i]]+value[i], values[i-1][j]);
}
}
}
//反向找出选出的背包
int j=maxValue;
for(int i=N;i>0;i--){
if(values[i][j]>values[i-1][j]){
System.out.print(i+" ");
j=j-value[i];
if(j<0) break;
}
}
in.close();
}
}
测试数据：
Sample Input
10 3
3 3
7 7
9 9
Sample Output
10
Sample Input
6 5
1 1
3 5
3 10
8 6
5 7
Sample Output
15