思路
首先注意到数据范围只有100,所以我这里选择二维dp
通过证明不难发现,能带走的最多的重量,无论是分几次拿走的,一定可以变成一次能拿走的方案。
表示前 i 个武器放入天平的两端差距为 j 的天平上武器重量的和的最大值
所以状态转移方程就是
for(int i = 1 ; i <= n ;++i){//1到n个数 for(int j = 0 ; j <= cnt ; ++j){//cnt表示能得到的最大重量 dp[i][j] = dp[i-1][j]; int tmp = max(dp[i-1][j+a[i]],dp[i-1][abs(j-a[i])]);//i-1个数分别向左天平和右天平加数 dp[i][j] = max(dp[i][j],tmp+a[i]);//更新最大值 } }
看转移方程应该就很好理解了,那我就给代码了
代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; inline ll read(){ ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); } while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar(); return s * w; } int a[105]; int dp[110][110005];//前i个差距为m的最大值 int main(){ int n = read() , m =read(); int cnt = 0; for(int i = 1 ;i <= n ; ++i ){ a[i] = read(); cnt += a[i]; } memset(dp,-0x3f,sizeof(dp)); dp[0][0] = 0; for(int i = 1 ; i <= n ;++i){ for(int j = 0 ; j <= cnt ; ++j){ dp[i][j] = dp[i-1][j]; int tmp = max(dp[i-1][j+a[i]],dp[i-1][abs(j-a[i])]); dp[i][j] = max(dp[i][j],tmp+a[i]); } } int ans = 0; for(int i = 0 ; i <= m ;++i){ ans = max(ans,dp[n][i]); } cout<<ans<<endl; }