【题目名称】0/1背包
一个旅行者有一个最多能装m公斤物品的背包，现在有n件物品，它们的重量分别是w1,w2,…,wn，它们的价值分别为c1,c2,…,cn。若每一种物品只有一件，求旅行者能获得的最大总价值。
【输入格式】
第一行：两个整数，m（背包容量，m<=200）和n(物品数量，n<=30)。
第二~n+1行：每行两个整数wi，ci，表示每个物品的重量和价值
【输出格式】
一个数据，表示最大总价值
【输入样例#1】
10 4
2 1
3 3
4 5
7 9
【输出样例#1】
12
import java.util.*;
public class Main {
static int m,n;
static int w[]=new int[30];
static int v[]=new int[30];
static int f[][]=new int[30][200];
public static int max(int x,int y){ //求x和y的最大值
if(x>y)
return x;
else
return y;
}
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
m=in.nextInt();
n=in.nextInt();
for(int i=1;i<=n;i++)
{
w[i]=in.nextInt();
v[i]=in.nextInt();
}
for(int i=1;i<=n;i++){ //f(i,x)表示前i件物品，总重量不超过x的最优价值
for(int x=1;x<=m;x++){
if(x>=w[i])
f[i][x]=max(f[i-1][x-w[i]]+v[i],f[i-1][x]);
else f[i][x]=f[i-1][x];
}
}
System.out.println(f[n][m]);
}
}