题目
小v最近在玩一款挖矿的游戏,该游戏介绍如下:
1、每次可以挖到多个矿石,每个矿石的重量都不一样,挖矿结束后需要通过一款平衡矿车运送下山;
2、平衡矿车有左右2个车厢,中间只有1个车轮沿着导轨滑到山下,且矿车只有在2个车厢重量完全相等且矿石数量相差不超过1个的情况下才能成功运送矿石,否则在转弯时可能出现侧翻。
假设小v挖到了n(n<100)个矿石,每个矿石重量不超过100,为了确保一次性将n个矿石都运送出去,一旦矿车的车厢重量不一样就需要购买配重砝码。请问小v每次最少需要购买多少重量的砝码呢? (假设车厢足够放下这些矿石和砝码,砝码重量任选)
解法
这道题我没做出来,感觉自己对于背包问题的解答思路还是比较欠缺的。所以写个文章梳理一下。下面是大佬AC的代码,n表示矿石数量,weight记录每块矿石的重量。
int solution(int n, int weight[]) { int s = 0; for (int i = 0; i < n; ++i) { s += weight[i]; } // S 为矿石总重量的一半 int S = s >> 1; // N 为矿石数量的一半 int N = (n + 1) >> 1; //建立(S+1)*(N+1)的动态二维数组 // dp[i][j] 代表什么呢 vector<vector<int> > dp(S + 1, vector<int>(N + 1, -INF)); // 数组第一行置为0 for (int i = 0; i <= S; ++i) dp[i][0] = 0; for (int i = 0; i < n; ++i) { auto dp1 = dp; // j的取值范围[ weight[i], S],为什么呢 for (int j = weight[i]; j <= S; ++j) { for (int k = 1; k <= N; ++k) { dp1[j][k] = max(dp1[j][k], dp[j - weight[i]][k - 1] + weight[i]); } } // 用旧的dp数组来进行for循环,循环完毕更新整个dp数组 swap(dp1, dp); } if (n & 1) { return s - 2 * max(dp[S][N], dp[S][N - 1]); } return s - 2 * dp[S][N]; }