https://ac.nowcoder.com/acm/problem/19158
题意:
有一个天平,每次只要放上去的东西重量相差不超过m即可拿走,问最多能带走物品的重量为多少?
分析:
在这个问题中,我们关心的只有两边的差值,如果两边差值小于等于m,那么天平就是等价的,那么对于当前差值j,你再加一件物品后的状态,只与之前的差值j有关,差值变成j+w[i],或abs(j-w[i]),因此对于当前a[i]物品,假定放进去最优解是差值为j的时候,那么这个最优解一定是从上一个状态的其中一个差值j转化过来的,我们需要从这过程中取最优情况,因此用dp进行解决。
dp[i][j]:表示前i个物品差值为j的最大重量。
转移状态: 不取当前物品: dp[i][j]=max(dp[i][j],dp[i-1][j])
取当前物品放在较重一侧: dp[i][j]=max(dp[i][j],dp[i-1][j+a[i]]+a[i])
取当前物品放在较轻一侧: dp[i][j]=max(dp[i][j],dp[i-1][abs(j-a[i])]+a[i])
最后得到 dp[n][j] 差值为j的前n个物品的最大重量
枚举所有j中取最大值即为最终答案。
代码:
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int n,m,i,j; int a[105]; int dp[105][10005];//第i个物品差值为j的最大容量 int main() { scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%d",&a[i]); } memset(dp,-1,sizeof(dp)); dp[0][0]=0; for(i=1;i<=n;i++){ for(j=0;j<=10001;j++){ if(dp[i-1][j]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j]);//不取,保留上状态 if(dp[i-1][j+a[i]]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][j+a[i]]+a[i]); //取了放重的一边 if(dp[i-1][abs(j-a[i])]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][abs(j-a[i])]+a[i]);//取了放轻的一边 } } int ans=0; for(i=0;i<=m;i++){ ans=max(dp[n][i],ans); } printf("%d",ans); }