当前位置:网站首页>Unbalance balance (dynamic programming, DP)
Unbalance balance (dynamic programming, DP)
2022-07-06 19:25:00 【surowvv】
Title Description
finally Alice Out of the trap of the demon king , But now she forgot to bring her weapon , What should I do ??? This is the time , A mysterious old man came up to her and promised to give her weapons for free , But the old man has one condition , You need to put the selected weapons on both ends of the scale , If the balance is balanced, all weapons on the balance can be taken away , Fortunately, the scale is rusty , As long as the weight difference between the two ends is less than or equal to m Will maintain balance ,Alice Foolishly think that the heavier the weapon, the better , seek Alice The maximum total weight of weapons that can be taken .( Unlimited number of operations )
Input description :
first line 2 It's an integer n, m; The second line n It's an integer x, respectively n The weight of a weapon . 1 <= n <= 100; 0 <= m <= 100; 1 <= x <= 100;
Output description :
An integer , Express Alice The maximum total weight of weapons that can be taken .
Example 1
Input
5 4 1 5 61 65 100
Output
132
Example 2
Input
5 0 10 20 30 40 100
Output
200
analysis :
dp[i][j] , In the i The difference between the two sides of the balance is j Maximum weight of
When not selected dp[i][j] = max(dp[i][j], dp[i - 1][j]);
Ipsilateral :dp[i][j + a[i]] = max(dp[i][j + a[i]], dp[i - 1][j] + a[i]);
Opposite side :dp[i][j - a[i]] = max(dp[i][j - a[i]], dp[i - 1][j] + a[i]);
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
int n, m;
int a[110];
int dp[110][10010];
int sum = 0;
const int inf = 0x3f3f3f3f;
int main()
{
cin >> n >> m;
memset(dp, -inf, sizeof(dp));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
dp[i][j + a[i]] = max(dp[i][j + a[i]], dp[i - 1][j] + a[i]);
dp[i][abs(j - a[i])] = max(dp[i][abs(j - a[i])], dp[i - 1][j] + a[i]);
}
}
int ans = 0;
for (int i = 0; i <= m; i++) ans = max(ans, dp[n][i]);
cout << ans;
return 0;
}
边栏推荐
- 安装Mysql报错:Could not create or access the registry key needed for the...
- LeetCode-1279. 红绿灯路口
- 学习探索-使用伪元素清除浮动元素造成的高度坍塌
- 五金机电行业智能供应链管理系统解决方案:数智化供应链为传统产业“造新血”
- R language uses the order function to sort the dataframe data, and descending sorting based on a single field (variable)
- Precautions for binding shortcut keys of QPushButton
- 今日直播 | “人玑协同 未来已来”2022弘玑生态伙伴大会蓄势待发
- 接雨水问题解析
- Use of map (the data of the list is assigned to the form, and the JSON comma separated display assignment)
- Problems encountered in using RT thread component fish
猜你喜欢
Meilu biological IPO was terminated: the annual revenue was 385million, and Chen Lin was the actual controller
Black Horse - - Redis Chapter
Problems encountered in using RT thread component fish
Analysis of frequent chain breaks in applications using Druid connection pools
思维导图+源代码+笔记+项目,字节跳动+京东+360+网易面试题整理
JDBC详解
The second day of rhcsa study
It's super detailed in history. It's too late for you to read this information if you want to find a job
Looting iii[post sequence traversal and backtracking + dynamic planning]
Carte de réflexion + code source + notes + projet, saut d'octets + jd + 360 + tri des questions d'entrevue Netease
随机推荐
short i =1; I=i+1 and short i=1; Difference of i+=1
Live broadcast today | the 2022 Hongji ecological partnership conference of "Renji collaboration has come" is ready to go
Is not a drawable (color or path): the vector graph downloaded externally cannot be called when it is put into mipmap, and the calling error program crashes
R language uses the order function to sort the dataframe data, and descending sorting based on a single field (variable)
Documents to be used in IC design process
Pychrm Community Edition calls matplotlib pyplot. Solution of imshow() function image not popping up
R language uses DT function to generate t-distribution density function data and plot function to visualize t-distribution density function data
Camel case with Hungarian notation
USB host driver - UVC swap
C language daily practice - day 22: Zero foundation learning dynamic planning
Mysql Information Schema 学习(二)--Innodb表
LeetCode_双指针_中等_61. 旋转链表
It's super detailed in history. It's too late for you to read this information if you want to find a job
Modulenotfounderror: no module named 'PIL' solution
10 schemes to ensure interface data security
Black Horse - - Redis Chapter
受益匪浅,安卓面试问题
Elastic search indexes are often deleted [closed] - elastic search indexes gets deleted frequently [closed]
应用使用Druid连接池经常性断链问题分析
史上超级详细,想找工作的你还不看这份资料就晚了