01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 ii 件物品的体积是 vivi，价值是 wiwi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入格式

第一行两个整数N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 ii 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

0 0

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String arg[]){
        Scanner scan=new Scanner(System.in);
        int N=scan.nextInt();//初始化N,V，并输入N,V
        int V=scan.nextInt();
        int[] v=new int[N+1];//初始化数组v[]，w[],并为其分配N+1个空间
        int[] w=new int[N+1]; 
        int[][] s=new int[N+1][V+1];//初始化二维数组s[i][j],该数组表示容量为j的背包，前i件物品的最高总价值
        s[0][0] = 0;
        for(int i=1;i<=N;i++){//循环遍历输入v,w数组
            v[i]=scan.nextInt();
            w[i]=scan.nextInt();
        }
        for(int i=1;i<=N;i++){
            for(int j=0;j<=V;j++){
                if(j                 s[i][j]=s[i-1][j];//前i件物品的最高总价值等于前i-1件物品的最高总价值，因为第i件物品放不进去
                else//如果放得下去，那么就要进行决策，决定拿或者不拿，也就是01问题
                s[i][j]=Math.max(s[i-1][j],s[i-1][j-v[i]]+w[i]);//不拿就是选择前i-1件物品的总价值，拿则是价值加上w[i],容量减去v[i]
            }
        }
        System.out.println(s[N][V]);//输出决策完后的结果
    }
}