套背包的模版,但是全WA了,求解
查看原帖
套背包的模版,但是全WA了,求解
1491219
user_888楼主2025/2/6 22:27
能过测试用例,但是过不了
/*测试数据2:
输入:
1 5 10 12
8 //8
9 12 23 10 1    //53//53-(23+1)=29
100 99 98 97 96 94 93 92 91 90 //明显只计算100,98,96,93,91
1 1 1 1 1 1 1 1 1 1 1 1 //6
输出:
521(8+29+478+6)
*/
#include<iostream>
using namespace std;
#include<cstring>
int s1,s2,s3,s4;
int dp[25][65], a[65];

int solve(int s) {
	int sum = 0;
	for (int i = 0;i < s;i++) { 
		cin >> a[i];
		sum += a[i];
	}

	for (int i = 0;i < s;i++) {
		for (int j = 0;j <= sum / 2;j++) {
			if (j>=a[i]) {
				dp[i+1][j] = max(dp[i][j], dp[i][j - a[i]]+a[i]);
			}
			else dp[i+1][j] = dp[i][j];
		}
	}
	int res= sum-dp[s][sum/2];
	memset(dp, 0, sizeof(dp));
	return res;
}
int main() {
	cin >> s1 >> s2 >> s3 >> s4;
	cout << solve(s1) + solve(s2) + solve(s3) + solve(s4);
	return 0;
}
2025/2/6 22:27
加载中...