背包问题之完全背包

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 = 1; i <= V; i++) {  //背包容量
 * 	    for (int j = 0; j < n; j++) { // 正序遍历dp数组(与01背包的差异之处在这里，V是背包容量，v[i]是没见商品的体积)
 * 		    // 如果要求恰好装入，需要if判断，否则不需要用这个判断语句
 * 		    if (i-v[j]>0&&dp[i - v[j]] != Integer.MIN_VALUE或Integer.MAX_VALUE) { //根据目标为最小/最大来选Integer.MIN_VALUE或者Integer.MAX_VALUE
 * 			    dp[i] = max或min(dp[i], dp[i - v[j]] + w[j]); //根据目标为最大/最小来选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];
        int[] w=new int[n];
        for(int i=0;i<n;i++){
            v[i]=sc.nextInt();//物品的体积
            w[i]=sc.nextInt();//物品的价值
        }
        int[] dp1=new int[V+1];//物品的最大价值，但不要求正好装满背包
        for(int i=1;i<=V;i++){
            for(int j=0;j<n;j++){
                if(i-v[j]>=0){
                    dp1[i]=Math.max(dp1[i],dp1[i-v[j]]+w[j]);
                }
            }
        }
        System.out.println(dp1[V]);
        int[] dp2=new int[V+1];//物品的最大价值，要求正好装满背包
        Arrays.fill(dp2,Integer.MIN_VALUE);//最大值这里就赋最小值，并且dp2[0]=0,后面比较用max
        dp2[0]=0;
        for(int i=1;i<=V;i++){ //背包容量或者物品为外循环都可以
            for(int j=0;j<n;j++){ //这里正序遍历
                if(i-v[j]>=0&&dp2[i-v[j]]!=Integer.MIN_VALUE){
                    dp2[i]=Math.max(dp2[i],dp2[i-v[j]]+w[j]);
                }
            }
        }
        System.out.println(dp2[V]<0?0:dp2[V]);
    }
}