lpc大菜逼 于 2020-06-21 22:27:31 发布不难想到这是一道01背包，首先我们假设背包体积为最佳血量（即是血量和 / 2），然后物品体积是猫猫的血量，由此我们的任务变成了从最多n / 2 + 1个物品中选出n个使得体积最接近总容量。需要一提的是一般遇到品均值这种题都要把最佳状态想成体积，然后不断尝试放入物品塞满背包从而达到最佳状态。
状态：dp[j][k]表示现可放j个物品，有k那么大的体积，求第i个物品能否放入
转移方程：if(dp[j][k]) {dp[j + 1][k + a[i].v] = 1;//若成立即可放入第i个物品 } 123 细节：
for(int i = sum;i >= 0; i--) {if(dp[n / 2][i] == 1 || (dp[n / 2 + 1][i] == 1 && n % 2 == 1)) {//最后只需判断这种方案是否成立即可printf("%d %d", i, u - i);return 0;}} 1234567 代码：
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int dp[205][100005], n, c[1000005]; struct jj{int v, m; }a[1000005]; int 123456789
