背包问题之01背包

package com.zhang.reflection.面试.算法模版.背包问题模版;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 你有一个背包，最多能容纳的体积是V。每个商品只能购买一次。
 *
 * 现在有n个物品，每种商品只有一个，第i个物品的体积为v_i，重量为w_i
 *
 * （1）求这个背包至多能装多大价值的物品？
 * （2）若背包恰好装满，求至多能装多大价值的物品？
 */

/**
 * 问题解题模版
 * (1)定义一维dp数组，初始化dp[0]=0;
 *    if (题目要求恰好装入背包):{
 * 	      if (求的是最大总价值){
 * 		     初始化为Integer.MIN_VALUE(注意dp[0]=0)
 *        }else if(求的是最小总价值){  //例如Coin Change
 * 		     初始化为Integer.MAX_VALUE
 *        }
 *    }else if(不要求恰好装满背包){
 * 		  初始化为0
 *    }
 *  (2)状态转移
 *  for (int i = 0; i < n; i++) {
 * 	    for (int j = V; j >= v[i]; j--) { // 逆序遍历dp数组(与完全背包的差异之处在这里，V是背包容量，v[i]是没见商品的体积)
 * 		    // 如果要求恰好装入，需要if判断，否则不需要用这个判断语句
 * 		    if (dp[j - v[i]] != Integer.MIN_VALUE或Integer.MAX_VALUE) { //根据目标为最小/最大来选Integer.MIN_VALUE或者Integer.MAX_VALUE
 * 			    dp[j] = max或min(dp[j], dp[j - v[i]] + w[i]); //根据目标为最大/最小来选max/min
 *          }
 *      }
 * }
 *
 */

public class 零一背包 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int V = sc.nextInt();
        //存放体积
        int[] v=new int[n+1];
        //存放价值
        int[] w=new int[n+1];
        for(int i=1;i<=n;i++){
            v[i]=sc.nextInt();
            w[i]=sc.nextInt();
        }
        //dp1[i]表示不考虑背包是否装满，在容量为i的情况下，最多装多大价值的物品
        int[] dp1=new int[V+1];
        for(int i=1;i<=n;i++){
            //由于每个物品只能用一次，为了防止重复计算，需要倒序遍历
            for(int j=V;j>=v[i];j--){
                //状态转移，要么选择第i件物品，要么不选，取价值最大的
                dp1[j]=Math.max(dp1[j-v[i]]+w[i],dp1[j]);
            }
        }
        System.out.println(dp1[V]);
      
//非优化版本
//        int[][] dp1=new int[n+1][V+1];
//        for(int i=1;i<=n;i++){
//            //由于每个物品只能用一次，为了防止重复计算，需要倒序遍历
//            for(int j=0;j<=V;j++){
//                //状态转移，要么选择第i件物品，要么不选，取价值最大的
//                if(v[i] > j)
//                    dp1[i][j] = dp1[i-1][j];
//                else
//                    dp1[i][j] = Math.max(dp1[i-1][j],dp1[i-1][j-v[i]]+w[i]);
//            }
//        }
//        System.out.println(dp1[n][V]);
        //逆推找出装入背包的所有商品的编号
//        int j=V;
//        String numStr="";
//        for(int i=n;i>0;i--){
//            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
//            if(dp1[i][j]>dp1[i-1][j]){
//                numStr = i+" "+numStr;
//                j=j-v[i-1];
//            }
//            if(j==0)
//                break;
//        }
      
      
      
        //dp2[i]表示背包恰好装满时，在容量为i的情况下，最多装多大价值的物品
        int[] dp2=new int[V+1];
        Arrays.fill(dp2,Integer.MIN_VALUE);
        //没有物品时，价值为0
        dp2[0]=0;
        for(int i=1;i<=n;i++){//物品个数为外循环
            //由于每个物品只能用一次，为了防止重复计算，需要倒序遍历
            for(int j=V;j>=v[i];j--){
                //状态转移，要么选择第i件物品，要么不选，如果减后的值为Integer.MIN_VALUE，不能从前一个状态转换，否则可以转换
                if(dp2[j-v[i]]!=Integer.MIN_VALUE){
                    dp2[j]=Math.max(dp2[j-v[i]]+w[i],dp2[j]);
                }
            }
        }
      //逆推找出装入背包的所有商品的编号
		int j=V;
		String numStr="";
		for(int i=N;i>0;i--){
			//若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
			if(dp[i][j]>dp[i-1][j]){
				numStr = i+" "+numStr;
				j=j-weight[i-1];
			}
			if(j==0)
				break;
		}
        System.out.println(dp2[V]<0?0:dp2[V]);
    }
}