龚秋志


私信TA

用户名:uq_48078956563

访问量:55049

签 名:

等  级
排  名 36
经  验 13973
参赛次数 30
文章发表 64
年  龄 19
在职情况 学生
学  校 湖北生物科技职业学院
专  业 计算机应用

  自我简介:

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] W = new int[N + 1];//重量
        int[] V = new int[N + 1];//价值
        int[] K = new int[N + 1];//数量
        for (int i = 1; i <= N; i++) {
            W[i] = sc.nextInt();
            V[i] = sc.nextInt();
            K[i] = sc.nextInt();
        }

        int[] dp = new int[M + 1];//滚动数组
        for (int j = 1; j <= N; j++) {
            for (int i = M; i >= 1; i--) {
                // W[j] * k <= i:W[j]当前物品的重量*物品数量K小于等于当前背包的容量i
                // k <= K[j]物品数量k小于等于当前物品j的个数
                for (int k = 1; W[j] * k <= i && k <= K[j]; k++) {
                    dp[i] = Math.max(dp[i], dp[i - W[j] * k] + k * V[j]);
                }
            }
        }

        System.out.println( dp[M]);

    }
}


 

0.0分

9 人评分

  评论区

非常棒
2020-10-09 09:35:48
!!!!!
2020-10-08 16:24:41
  • «
  • 1
  • »