01背包，多重背包，完全背包JAVA实现

package beibao;

public class bagQuestion {
    public static void main(String[] args) {
        int number=4;
        int[] weight= { 1,3,4,2};
        int[] value= { 1500,3000,2000,3500};
        int capacity=4;
        int[][] dp=new int[number+1][number+1];
        int[] num= {2,1,3,1};
        System.out.println(bag3(capacity, weight, value));
        System.out.println(bag4(capacity, weight, value,num));
        for(int i=1;i<dp.length;i++) {
            for(int j=1;j<dp[0].length;j++) {
                if(weight[i-1]>j) {
                    dp[i][j]=dp[i-1][j];
                }else {
                    dp[i][j]=Math.max(dp[i-1][j], value[i-1]+dp[i-1][j-weight[i-1]]);
                }
            }
        }
        for(int i=0;i<dp.length;i++) {
            for(int j=0;j<dp[0].length;j++) {
                System.out.print(dp[i][j]+" ");
            }
            System.out.println();
        }
        int j=capacity;
        String numStr="";
        for(int i=number;i>0;i--) {
            if(dp[i][j]>dp[i-1][j]) {
                numStr=i+" "+numStr;
                j -=weight[i-1];
            }
            if(j==0)
                break;
        }
        System.out.println(numStr);
    }
    //0-1背包问题
    public static int bag2(int W,int[] w,int[] v) {
        int[] f=new int[W+1];
        for(int i=1;i<W+1;i++) {
            for(int j=W;j>=w[i-1];j--) {
                f[j]=Math.max(f[j], f[j-w[i-1]]+v[i-1]);
            }
        }
        return f[W];
    }
    //完全背包问题(物品没有数量限制)
    public static int bag3(int W,int[] w,int[] v) {
        //第一种方法
        int[] f=new int[W+1];
        for(int i=1;i<W+1;i++) {
            for(int j=w[i-1];j<=W;j++) {
                f[j]=Math.max(f[j],f[j-w[i-1]]+v[i-1]);
            }
        }
        return f[W];
        //第二种方法
//        int n = w.length - 1;// 第一个值，不算
//        int[] f = new int[W + 1];
//        for (int i = 1; i <= n; i++)
//            for (int j = w[i]; j <= W; j++)
//                f[j] = Math.max(f[j], f[j - w[i]] + v[i]);
//        return f[W]; // 最优解
    }


    //完全背包问题(物品有数量限制)多重背包问题
    public static int bag4(int W,int[] w,int[] v,int[] num) {
        int[] f=new int[W+1];
        for(int i=1;i<=w.length;i++) {
            for(int j=W;j>=w[i-1];j--) {
                for(int k=0;k<=num[i-1]&&j-k*w[i-1]>=0;k++) {
                    f[j]=Math.max(f[j], f[j-k*w[i-1]]+k*v[i-1]);
                }
            }
        }
        return f[W];
    }
}