Golden Calculation: optimize the value in your backpack with the ability to crus...
source link: https://codeforces.com/blog/entry/124398
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Golden Calculation: optimize the value in your backpack with the ability to crush ingots!
By Vectrizz, 13 hours ago,
You have n bars of gold, each with a different weight and value. You also have a backpack of capacity S. You need to calculate the maximum total value of the bars that you can get. You can crush the ingots. In this case, the value of the ingot will decrease proportionally to the weight of the ingot. Input data
The first line contains two integers S and N (1≤S≤1e4; 1≤N≤300).
The second line contains n integers — the weights of ingots. Each ingot has a non-negative weight not exceeding 1e5 The third line contains n more integers — ingot values. Each ingot has a non-negative value not exceeding 1e5. .
Output data
Print a single number — the maximum total value you can carry. If the answer is not an integer, round it up to the nearest integer.
Sample Input:
8 4
2 4 4 7
2 5 5 9
Sample Output:
11
If you have any ideas how to solve this problem, feel free to write your suggestions
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK