Niuke real problem programming - day14

Programming environment ：c++

1、 String value

describe ： There is an interesting way to calculate the value of strings : Count the number of occurrences of each character in the string , Then find the sum of the squares of the number of all characters as the value of the string
for example : character string "abacaba", includes 4 individual 'a',2 individual 'b',1 individual 'c', So the value of this string is 4 * 4 + 2 * 2 + 1 * 1 = 21
Niuniu has a string s, And allow you to start from s Remove up to k Characters , Your goal is to minimize the value of the resulting string .

Algorithmic thought ：

According to the title requirements , To remove the fixed number of characters , Strings are the least valuable , Then each time you remove the character that appears the most times in the current string . First, count the number of characters in the string , After removing one at a time , You need to reorder the array that counts the number of character occurrences , Make sure that each overflow is the string with the most occurrences . Finally, according to the string value formula , Calculate the minimum value of the final string .

Part of the code implementation ：

2、 Under the kitchen

describe ：

Niuniu wants to try some new dishes , Each dish needs some different materials , Ask how many different materials need to be prepared to complete all the dishes .

Input description ： Each input contains 1 Test cases . The... Of each test case i That's ok , To complete the first i What materials are needed for this dish , Each material is separated by a space , The input contains only uppercase letters and spaces , Input files do not exceed 50 That's ok , No more than... Per line 50 Characters .

Algorithmic thought ：

The number of lines entered in the title is uncertain , You need to decide whether there is any string input , Here I omit the concept of line , Store all the ingredients you need into a string array . For all ingredients , We need to de duplicate it , Get the number of ingredients you need to prepare . First, sort all strings , Then the same ingredients will come together , Traverse the sorted string array , When adjacent elements are different , It represents different ingredients （ Count +1）. The number of ingredients required after weight removal is obtained after traversal .

3、 Asset package packaging

describe ：

In financial asset transactions , It often involves the selection and packaging of asset packages . In the process of asset package packaging , Each type of asset has a fixed quantity and value , You need to select some assets to package , Maximize the total value of the asset package . When packaging, each asset can only be packaged as a whole , Indivisible . It is assumed that the existing can accommodate M Asset package of assets , In addition, there are N Types of assets . assets Na The number of Ta strip , The total value is Va element ; assets Nb The number of Tb strip , The total value is Vb element ; assets Nc The number of Tc strip , The total value is Vc element ......; assets Nn The number of Tn, The total value is Vn. Write algorithms , Choosing which types of assets to put into the asset package can maximize the total value of the asset package ？

Algorithmic thought ：

Because the asset package can only be placed as a whole or not , So the topic is actually a 0/1 Dynamic programming of knapsack . set up j Is the total capacity ,wi For the first time i The weight of each item . If the total capacity of the backpack j Less than i Space occupied by items , The maximum value that can be obtained at this time is equivalent to considering 1 To the first i-1 The total storage capacity of items is j The backpack . otherwise , You can choose to put it or not i Item ： If you don't put the first i Item , At this time, the maximum value and only put the front i-1 Same piece ; The first i When items are put into the backpack , The total capacity is j Your backpack must be allocated wi Space for i Item , And before the first 1 To the first i-1 Items can only be placed with a total capacity of j-wi In my backpack , The greater of the two cases . Initialize a result array dp, There's recursion ：dp(i,j)=max {dp(i-1, j),dp(i-1, j-w)+vi}

The code part implements ：