背包问题

import java.io.*;

/**
* 完全背包问题,基本思路，时间复杂度较高，使用二维数组
*/
     public class ceshi 
        {
    //v为容量，n为种类
    static int v,n;
    //p[]为价格
    static int p[];
    //w[]为价值
    static int w[];
    //转行键入BufferedReader
    public static void main(String[] args)throws Exception
{
    BufferedReader buffer =new BufferedReader(new InputStreamReader(System.in));
    v=Integer.parseInt(buffer.readLine());
    n=Integer.parseInt(buffer.readLine());
    p=new int[n+1];
    w=new int[n+1];
    for(int i=0;i<n;i++)
    {
        String[] ss=buffer.readLine().split(" ");
        p[i+1]=Integer.parseInt(ss[0]);
        w[i+1]=Integer.parseInt(ss[1]);
    }
    max();
}

public static void max()
{
    //f[i][j]为第i 个种类在容量剩余j为时的前面累加的最大价值
    int[][] f=new int[n+1][v+1];
    //i为种类
    for(int i=1;i<=n;i++)
    {
        //遍历到i种类时的剩余容量j
        for(int j=0;j<=v;j++)
        {
            //k为i种类的要取得数量
            for(int k=0;k<=v/p[i];k++)
            {
                if(j>=k*p[i])
                {
                    //f[i][j]为第i-1种类时容量为j-k*p[i]的最优价值加上i种类取K个的价值
                    f[i][j]=Math.max(f[i-1][j-k*p[i]]+k*w[i], f[i][j]);
                }
                else
                {
                    f[i][j]=f[i][j];
                }

            }
        }
    }
    System.out.println(f[n][v]);
}

}