Topic describes

Wang Qiang is very happy today, the company gave N yuan year-end bonus. Wang Qiang decided to spend his year-end bonus on shopping. He divided the items he wanted to buy into two categories: main parts and accessories. The accessories belong to a certain main part. Main accessory Computer printer, scanner bookcase book desk lamp, stationery work chair None If you want to buy an item classified as an accessory, you must first buy the main accessory. Each master piece can have 0, 1, or 2 attachments. Attachments no longer have attachments that are subordinate to them. Wang Qiang wanted to buy a lot of things, in order to stay within his budget, he assigned each item a importance scale of 5. They were expressed as integers from 1 to 5, with the fifth grade being the most important. He also looked up the price of each item on the Internet (all rounded multiples of 10 yuan). He wanted to maximize the sum of the product of the price and importance of each item without exceeding N dollars (it could be equal to N dollars). Let the price of item J be v[j], and the importance of item J be W [j]. A total of K items were selected, and their numbers were J 1, J 2... , j k, then the sum of the results is: v[j 1]*w[j 1]+v[j 2]*w[j 2]+... +v[j k]* W [j k]. Please help Wang Qiang to design a shopping list that meets the requirements. Input description: The first line of input is two positive integers separated by a space: N m (where N (<32000) is the total amount of money, and m (<60) is the number of items you want to buy.) From line 2 to line M +1, line J gives the basic data of the item numbered J-1, each line has 3 non-negative integers V p q (where V represents the price of the item (v<10000), p represents the importance of the item (1-5), Q indicates whether the item is a main or an accessory. If q=0, it means that the item is the main one; if Q >0, it means that the item is an attachment and Q is the number of the main one.) Output description: The output file has only a positive integer, which is the maximum value (<200000) of the sum of the product of the price and importance of the item that does not exceed the total amount of money.Copy the code

Train of thought

  • Int [] TMP; int[] TMP; (It can be optimized to not cycle dp calculation when there is no attachment)
  • In has been selected(dp [I]! = 0)Or not at all(I == 0)The case for mergingtmpanddpTMP indicates all possibilities, optional or not
  • Calculate the index of dp, which is the current total amount, and retain the largest value when the value and price are the same
  • And then you calculate the highest possible value

code

import java.util.Scanner; import java.util.ArrayList; import java.util.List; // Note that the class name must be Main, Public class Main {public static void Main (String[] args) {Scanner in = new Scanner(system.in); While (in.hasNextline ()) {String s = in.nextline (); if (s.isEmpty()) { return; } String[] strArray = s.split(" "); int n = Integer.parseInt(strArray[0])/10; int m = Integer.parseInt(strArray[1]); Goods[] goods = new Goods[m]; for (int i = 0; i < m; i++) { strArray = in.nextLine().split(" "); Goods tmp = new Goods(Integer.parseInt(strArray[2]), Integer.parseInt(strArray[0])/10, Integer.parseInt(strArray[1]), new ArrayList<>()); if (tmp.master > 0) { goods[tmp.master - 1].list.add(tmp); } goods[i] = tmp; } System.out.println(shopDp(goods, n) * 10); } } static class Goods { Goods(int master, int price, int value, List<Goods> list) { this.master = master; this.price = price; this.value = value; this.list = list; } int master; int value; int price; List<Goods> list; } private static int shopDp(Goods[] goods, int n) { int[] dp = new int[n + 1]; for (Goods item : goods) { if (item.master > 0) { continue; Int [] TMP = new int[n + 1]; tmp[item.price] = item.price * item.value; For (Goods child: item.list) {// Max (I) = n-child. price for (int I = n-child. price; i >= 0; i--) { if (tmp[i] > 0) { int price = child.price + i; tmp[price] = Math.max(tmp[i] + child.price * child.value, tmp[price]); } } } // dp for (int i = n; i >= 0; i--) { if (dp[i] == 0 && i ! = 0) { continue; } Max (j) = n-i for (int j = n-i; j >= 0; j--) { if (tmp[j] ! = 0) { dp[i + j] = Math.max(dp[i] + tmp[j], dp[i + j]); } } } } int ret = -1; for (int i = n; i >= 0; i--) { if (dp[i] ! = 0) { ret = Math.max(ret, dp[i]); } } return ret; }}Copy the code