洛谷P2392--01背包
程序员文章站
2022-06-08 14:30:38
...
这题和之前遇到过的一题很像,先看一下那一题
题目意思就是给你一个数,让你把这个数组分成两个数组,然后让这两个数组中较小的那一个的和尽量大(也可以想成让两者中较大的那一个尽量小),最优解一定是原数组的sum/2,其实就是容量为sum/2的背包取拿这些wi 等于 ai,vi也等于ai的物品取到的最大值
//dp[j] = max(dp[j],dp[j-A[i].w]+A[i].v);
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+10;
int n,dp[N],w[N],v[N];
int main(){
while(~scanf("%d",&n)){
int sum = 0;
memset(dp,0,sizeof(dp));
for(int i = 1;i <= n;i++){
scanf("%d",w+i);
v[i] = w[i];
sum+=w[i];
}
for(int i = 1;i <= n;i++){
for(int c = sum/2;c >= 0;c--){
if(c >= w[i]){
dp[c] = max(dp[c],dp[c-w[i]]+v[i]);
}
}
}
printf("%d\n",dp[sum/2]);
}
return 0;
}
然后再回到洛谷P2392,先一个科目地想,对于一道题目要么把它放进左脑,要么把它放进右脑,一个科目一共有2^s种情况,然后取其中右脑和左脑中较大值最小的那种情况最优,其实就和上面那题一样,只不过这次要求sum-dp[sum/2],因此只需要做四次01背包即可
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int s[4];
int w[25],dp[2000];
int solve(int n){
int sum = 0;
memset(dp,0,sizeof(dp));
for(int i = 1;i <= n;i++){
scanf("%d",w+i);
sum+=w[i];
}
for(int i = 1;i <= n;i++){
for(int c = sum/2;c >= 0;c--){
if(c >= w[i]){
dp[c] = max(dp[c],dp[c-w[i]]+w[i]);
}
}
}
return sum-dp[sum/2];
}
int main(){
for(int i = 0;i < 4;i++) scanf("%d",s+i);
int ans = 0;
for(int i = 0;i < 4;i++) ans+=solve(s[i]);
printf("%d\n",ans);
return 0;
}
上一篇: SQL行号排序和分页(SQL查询中插入行号 自定义分页的另类实现)
下一篇: 程序员何去何从