Java 代码

package com.company.ForTruth.ali.背包问题;

import java.util.Scanner;

/**
 * Author:   hszzjs
 * Date:     2019/5/10 13:09
 * E-mail:   hushaozhe@stu.xidian.edu.cn
 * 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
 第 i 件物品的体积是 vi，价值是 wi。
 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
 输出最大价值。
 输入格式
 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
 输出格式
 输出一个整数，表示最大价值。
 数据范围
 0<N,V≤1000
 0<vi,wi≤1000
 输入样例
 4 5
 1 2
 2 4
 3 4
 4 5
 输出样例：
 8
 参考链接：https://blog.csdn.net/qq_38410730/article/details/81667885
 */
public class 背包01 {
    /**
     * 简单背包问题（N个物体，V的容量）：基于动态规划，那么就必须知道状态方程。Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，
     * 定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，那么要到V(i,j)（即第i个商品还没有装进去），
     * 就是要么Wi>j，必然是放不进去了，所以V(i,j)=V(i-1,j)，要么j>=w(i)，两种选择：放进去与不放，只要找到
     * 最大值即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。那么根据这个关系递推就可以。
     * 这个状态矩阵的大小需要是int[N+1][V+1].默认j=0，以及i=0的时候状态是0
     */
    static class VW{///表示物体性质
        int v,w;
        public VW(int v,int w){
            this.v=v;
            this.w=w;
        }
    }

    /**
     * 关于到底是正序还是逆序问题，我没有搞明白，反正正序和逆序都是通过了的，但是既然大家都说01背包是逆序，那就逆序吧
     * @param args
     */
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt(),V=sc.nextInt();
        VW[] vw=new VW[N];
        for(int i=0;i<N;i++){
            vw[i]=new VW(sc.nextInt(),sc.nextInt());
        }
        int[][] res=new int[N+1][V+1];
//        for(int i=1;i<=N;i++){
//            for(int j=1;j<=V;j++){
//                if(vw[i-1].v>j) res[i][j]=res[i-1][j];
//                else res[i][j]=Math.max(res[i-1][j],res[i-1][j-vw[i-1].v]+vw[i-1].w);
////                System.out.println(i+"=="+j+"=="+res[i][j]);
//            }
////            System.out.println();
//        }
        for(int i=1;i<=N;i++){
            for(int j=V;j>0;j--){
                if(vw[i-1].v>j) res[i][j]=res[i-1][j];
                else res[i][j]=Math.max(res[i-1][j],res[i-1][j-vw[i-1].v]+vw[i-1].w);
            }
        }
        System.out.println(res[N][V]);
    }
}