题目 1924: 蓝桥杯-01背包

题目描述:

给定N个物品,每个物品有一个重量W和一个价值V.你有一个能装M重量的背包.问怎么装使得所装价值最大.每个物品只有一个.

代码:

package lanqiao;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int weight = sc.nextInt();
        int[] v = new int[num + 1];
        int[] w = new int[num + 1];
        int[][] dp = new int[num +1][weight + 1];
        for(int i = 1;i <= num;i ++)
        {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        for(int i = 1;i <= num;i ++)
        {
            for(int j = 1;j <= weight;j ++)
            {
                if(j < w[i])
                {
                    dp[i][j] = dp[i - 1][j];
                }
                else{
                    dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - w[i]] + v[i]);
                }
            }
        }

        System.out.println(dp[num][weight]);
    }
}