題目
有若干塊大理石，其大小及美觀程度不一，為了比較客觀的分割這些大理石，我們需要先給這些大理石一個評分，評分分為6個等級，分別用1~6的數字來表示，現希望將這些大理石分成兩部分，使每部分的評分之和相同，
輸入：
輸入一行，包括6個數，分別是每個等級的大理石的數量，每種等級的大理石數量不超過20000.
輸出：
如果這些大理石能否分割成評價等級之和相同的兩部分，則輸出true，否則輸出false.
樣例輸入：
1 0 1 2 0 0
樣例輸出：
false
要求
1、寫出求解樣例輸入時的求解程序，
2、寫出演算法分析程序，撰寫程式求解上述問題，并分析演算法的時間復雜度，
參考鏈接
這是力扣關于01背包的講解，看懂了就知道怎么做這道題了，
https://leetcode-cn.com/problems/partition-equal-subset-sum/solution/fen-ge-deng-he-zi-ji-by-leetcode-solution/
分析
本題是多重背包問題，只要會01背包就能做多重背包，所以，我們不用遞回，用動態規劃來做，只用填一張二維表，先不說為什么，
題目輸入是“1 0 1 2 0 0”，也就是有1個等級為1的大理石，有1個等級為3的，有2個等級為4的，把它轉化為大理石的陣列：num=[1，3，4，4]，要分割為兩半，則每一部分是(1+3+4+4)/2=6個等級，用這四個數能湊出6我們就能回傳true，
現在構建二維表，我們用二維陣列dp[][]表示，行是大理石陣列num的元素，列是需要湊出的等級，表格則是判斷true還是false，如果我們只湊6，為什么要把1到5都寫出來呢，后面再說，
| num | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | ||||||
| 3 | ||||||
| 4 | ||||||
| 4 |
現在開始一行一行地填表，
1、填第一行的時候，第一個空格代表背包里只有1，要湊出1，明顯是可以的，dp[num[0]][1]填true，后面的2到6是湊不出來的，都是false，
2、填第二行的時候，注意，這里不是背包里只有3的意思，而是1和3，
3、填第三行的時候，代表背包里有1，3，4，
4、填第四行的時候，代表背包里有1，3，4，4
所以，為什么湊6需要把1-5都列出來，就是為了查背包里有沒有其他大理石能和當前大理石一起湊到某個數，
第一行我們總是只能填一個T，就是行=列的時候，因為一個數只能湊它本身的數，在填第二行的時候，對于小于3的列，直接照抄上一行；對于等于3的列，直接填T；對于大于3的列，用列減3得到的差，去查上一行且列等于這個差的格子（也就是看背包里有沒有等于這個差的數），如果是T，代表背包里有這個數，填T，如果是F代表背包里沒有這個數，填F，
完整代碼如下：（時間緊迫，不注釋了，想著那個填表就知道咋寫了）
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 120000
bool distribution(int* num, int numSize);
int main()
{
int num[MAXN]={0};
int n;
int cnt=0;
// 輸入6個數
for(int i=1;i<=6;i++)
{
scanf("%d",&n);
// 多重背包陣列轉01背包陣列，也就是每個大理石的等級組成的陣列
for(int j=0;j<n;j++)
{
num[cnt]=i;
cnt++;
}
}
// 大理石陣列，和它的長度傳進去
if(distribution(num,cnt))
printf("true");
else
printf("false");
return 0;
}
// 填表
bool distribution(int* num, int numSize)
{
// 只有1塊大理石湊啥啊還，裂成兩半吧
if (numSize < 2) {
return false;
}
int sum = 0, maxNum = 0;
// 大理石的等級加起來
for (int i = 0; i < numSize; ++i) {
sum += num[i];
maxNum = fmax(maxNum, num[i]);
}
// 大理石的等級加起來是奇數湊啥啊還，走走走
if (sum & 1) {
return false;
}
// 大理石等級和的一半才是最終要湊出的數
int target = sum / 2;
// 啥，連最大那塊大理石都比目標數大？湊啥啊還
if (maxNum > target) {
return false;
}
// 表來了，就是它，二維陣列dp
int dp[numSize][target + 1];
// 初始化dp為全F
memset(dp, 0, sizeof(dp));
// 填第一行，行和列相等的就是T
dp[0][num[0]] = true;
// 從第二行開始填
for (int i = 1; i < numSize; i++) {
int row = num[i];
for (int j = 1; j <= target; j++) {
// 列的數大于行的數，用列減去當前行的差，去找上一行列數等于這個差的狀態
if (j >= row) {
dp[i][j] = dp[i - 1][j] | dp[i - 1][j - row];
// 列數小于行數，直接照抄上一行
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
// 回傳表格右下角那個格，因為一旦上一行為T，后面所有行都為T
return dp[numSize - 1][target];
}
演算法的時間復雜度為
這不是最優的，最優的是把dp變成一維陣列，因為某個格子是T，則同列的后面每行都是T，所以dp不是二維的也可以，這種辦法的時間復雜度變成 ，時間關系就不再講了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/247244.html
標籤：其他
上一篇：進階版三子棋（待改進）
下一篇：第十二屆藍橋杯一月校內模擬賽題解