# 动态规划问题（01背包解法模板）

package javatest;
/**
 * 牛客面试规则，代码必须齐全
 * import java.util.Scanner;
 * Scanner sc = new Scanner (System.in);
 * 读一个整数：int n = sc.nextInt();
 * <p>
 * 读一个字符串：String s = sc.next();（以空格作为分隔符）
 * <p>
 * 读一个浮点数：double t =sc.nextDouble();
 * <p>
 * 读一整行：String s = sc.nextLine();
 * <p>
 * 判断是否有下一个输入可以用sc.hasNext()或sc.hasNextInt()或sc.hasNextDouble()或sc.hasNextLine()
 * <p>
 * 2. 输出
 * System.out.println();//换行打印，输出之后会自动换行
 * System.out.print();//不换行打印
 * System.out.printf();//按格式输出
 */

import javax.naming.LimitExceededException;
import java.lang.reflect.Type;
import java.util.*;

public class Main {

    /**
     * 8 5
     * 3 4
     * 5 5
     * 1 2
     * 2 1
     * 2 3
     */


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入可用limit数、项目数：");
        int limit = scanner.nextInt()+1;
        int length = scanner.nextInt();
        int[] getvalues= new int[length];
        int[] costs= new int[length];
        for (int i = 0; i < getvalues.length; i++) {
            costs[i] = scanner.nextInt();
            getvalues[i] = scanner.nextInt();
        }


        Bag01(limit,length,getvalues,costs);
    }

    /**
     * 01背包问题通用dp模板（动态规划）
     * @param limit
     * @param length
     * @param getvalues
     * @param costs
     */
    static void Bag01(int limit,int length,int []getvalues,int []costs){

        int dp[][]=new int[length][limit];
        for (int i = 0; i < getvalues.length; i++) {
            for (int j = 0; j < limit; j++) {
                if (j < costs[i]) {
                    dp[i][j] = 0;
                } else {
                    if(i==0){
                        dp[i][j]=getvalues[i];
                    }else{
                        if(dp[i-1][j-costs[i]]+getvalues[i]>dp[i-1][j]){
                            dp[i][j]=dp[i-1][j-costs[i]]+getvalues[i];
                        }else{
                            dp[i][j]=dp[i-1][j];
                        }
                    }
                }
            }
        }
        for (int i = 0; i < getvalues.length; i++) {
            for (int j = 0; j < limit; j++) {
                System.out.printf("%-6d",dp[i][j]);
            }
            System.out.println();
        }
        Stack stack = new Stack();
        int nowvalue=dp[length-1][limit-1];
        int pi=length-1;
        int pj=limit-1;
        while(nowvalue!=0){
            if(dp[pi][pj]!=dp[pi-1][pj]){
                stack.push((pi+1));
                pj-=costs[pi];
                pi-=1;
                nowvalue=dp[pi][pj];
            }else{
                pi-=1;
            }
        }
        while(stack.size()>0){
            System.out.println("第："+stack.pop());
        }
        System.out.println("最优解："+dp[length-1][limit-1]);
    }
}


 
        Copied!