欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

疯狂的采药—洛谷

程序员文章站 2022-07-16 12:30:21
...

题目:
疯狂的采药—洛谷
疯狂的采药—洛谷
思路:
完全背包的模板,但是需要空间优化,否则过不了。
代码:


import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        int m=sc.nextInt();
        int[] tt=new int[m];
        int[] v=new int[m];
        for (int i = 0; i < m; i++) {
            tt[i]=sc.nextInt();
            v[i]=sc.nextInt();
        }
        System.out.println(dp(t,m,tt,v));
    }

    private static int dp(int t,int m,int[] tt,int[] v) {
//        int[][] dp=new int[m][t+1];
//        for (int i = 0; i <= t; i++) {
//            dp[0][i]=i/tt[0]*v[0];
//        }
//        for (int i = 1; i < m; i++) {
//            for (int j = 0; j <= t; j++) {
//                for (int k = 0; k*tt[i]<=j ; k++) {
//                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-k*tt[i]]+k*v[i]);
//                }
//            }
//        }
        int [] dp=new int[1100000];
        for (int i = 0; i < m; i++) {
            for (int j =tt[i]; j <= t ; j++) {
                dp[j]=Math.max(dp[j],dp[j-tt[i]]+v[i]);
            }
        }
        return dp[t];
    }

}

相关标签: 动态规划和贪心