背包問題（2）：0/1背包

来源:https://www.cnblogs.com/cs-whut/archive/2022/03/30/16078393.html
-Advertisement-
Play Games

前言： 請各大網友尊重本人原創知識分享，謹記本人博客：南國以南i 上篇我們介紹到 保姆教程系列一、Linux搭建Nacos 註冊中心原理 一、環境準備 Java版本：1.8+ (Linux centos7虛擬機下安裝Jdk1.8) MySQL服務：5.6.5+ (Linux Centos7 安裝My ...


        0/1背包是最基本的背包問題，其基本特點是：每種物品僅有一件，可以選擇放或不放，即每個物品最多只能放一次。

        0/1背包問題的一般描述為：有N個物品，第i個物品的重量與價值分別為W[i]與P[i]。背包容量為V，試問在每個物品最多使用一次（物品必須保持完整）的情況下，如何讓背包裝入的物品具有更大的價值總和。

        其一般解題思路為：

        設f[i][j]表示容量為j時放入前i個物品得到的最大價值。

        對於第i件物品，有兩種選擇，即放或者不放。

        如果不放，則f[i][j]=f[i-1][j]；

        如果放，則f[i][j]=f[i-1][j-W[i]]+P[i]

        因此有狀態轉移方程：f[i][j]=max (f[i-1][j], f[i-1][j-W[i]]+P[i])。

        編寫代碼時，一般可以寫成如下的迴圈。

    for  (i=1;i<=N;i++)       // 對每件物品進行處理

        for (j=1;j<=V;j++)   

        {

           if (j-W[i]<0)

              f[i][j]=f[i-1][j];

           else

           {

               f[i][j]=max(f[i-1][j],f[i-1][j-W[i]]+P[i]);

           }

        }

最優值為f[N][V]。

        由上面的迴圈過程可知，迴圈過程中的f[i][j]僅與f[i-1][j]或f[i-1][j-W[i]]相關，因此可以將存儲空間由二維數組壓縮成一維數組，即

            f[j]=max（f[j], f[j−W[i]]+P[i]）

        在具體遞推處理時，需要採用逆推的方法進行計算最優值。一般寫成如下的迴圈。

    for  (i=1;i<=N;i++)        // 對每件物品進行處理

        for (j=V;j>=W[i];j--)    // 逆推計算最優值

        {

               f[j]=max(f[j],f[j-W[i]]+P[i]);

        }

        對於背包問題，數組f的初始化也需要註意。對於不同的問題，初始化值一般不同。

        一般在求最優解的背包問題題目中，有兩種不太相同的問法。有的題目要求“恰好裝滿背包”時的最優解，有的題目則並沒有要求必須把背包裝滿。這兩種問法的實現方法在初始化的時候就有所不同。

        如果是要求“恰好裝滿背包”，那麼在初始化時，除了f[0]為0，其它元素f[1]~f[V]均初始化為-∞，這樣就可以保證最終得到的f[V]是一種恰好裝滿背包的最優解。

        如果並沒有要求必須把背包裝滿，而是只希望獲得的價值儘量大，初始化時應該將f[0]~f[V]全部設為0。

        為什麼要這樣初始化呢？

        初始化f數組事實上就是在沒有任何物品放入背包時的合法狀態。如果要求背包“恰好裝滿”，那麼此時只有容量為0的背包可能被價值為0的nothing“恰好裝滿”，其它容量的背包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果背包並非必須被裝滿，那麼任何容量的背包都有一個合法解“什麼都不裝”，這個解的價值為0，所以初始時f的值也就全部為0了。

        0/1背包問題是最基本的背包問題，它包含了背包問題中設計狀態、確定狀態轉移方程的最基本思想，另外，其他類型的背包問題往往也可以轉換成0/1背包問題求解。因此需要認真體會並掌握。

【例1】採藥

問題描述

辰辰是個天資聰穎的孩子，他的夢想是成為世界上最偉大的醫師。為此，他想拜附近最有威望的醫師為師。醫師為了判斷他的資質，給他出了一個難題。醫師把他帶到一個到處都是草藥的山洞里對他說：“孩子，這個山洞里有一些不同的草藥，採每一株都需要一些時間，每一株也有它自身的價值。我會給你一段時間，在這段時間里，你可以採到一些草藥。如果你是一個聰明的孩子，你應該可以讓採到的草藥的總價值最大。”

如果你是辰辰，你能完成這個任務嗎？

輸入

第一行有2個整數 T（1≤T≤1000）和M（1≤M≤100），用一個空格隔開，T代表總共能夠用來採藥的時間，M 代表山洞里的草藥的數目。

接下來的 M行每行包括兩個在1到 100 之間（包括 1和100）的整數，分別表示採摘某株草藥的時間和這株草藥的價值。

輸出

輸出在規定的時間內可以採到的草藥的最大總價值。

輸入樣例

70 3

71 100

69 1

1 2

輸出樣例

3

        （1）編程思路。

        這是一道典型的0/1背包問題，把採摘每株草藥的時間看做標準模型中的重量，把規定的時間看做載重為T的背包，這樣問題和基本模型就一樣了。

        分別採用二維數組和一維數組的方法編寫源程式如下。

        （2）採用二維數組編寫的源程式1。

#include <stdio.h>
int max(int a,int b)
{
    if (a>b) return a;
    else  return b;
}
int main()
{
    int f[101][1001]={0};
    int w[101],v[101];
    int t,m;
    scanf("%d%d",&t,&m);
    int i,j;
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&w[i],&v[i]);
    }
    for (i=1;i<=m;i++)
        for (j=1;j<=t;j++)
        {
           if (j-w[i]<0)
              f[i][j]=f[i-1][j];
           else
           {
               f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
           }
        }
    printf("%d\n",f[m][t]);
    return 0;
}

        （3）採用一維數組編寫的源程式2。

#include <stdio.h>
int max(int a,int b)
{
    if (a>b) return a;
    else  return b;
}
int main()
{
    int f[1001]={0};
    int w[101],v[101];
    int t,m;
    scanf("%d%d",&t,&m);
    int i,j;
    for (i=1;i<=m;i++)
    {
        scanf("%d%d",&w[i],&v[i]);
    }
    for (i=1;i<=m;i++)
        for (j=t;j>=w[i];j--)
        {
               f[j]=max(f[j],f[j-w[i]]+v[i]);
        }
    printf("%d\n",f[t]);
    return 0;
}

        將上面的源程式提交給洛谷題庫P1048 [NOIP2005 普及組] 採藥（https://www.luogu.com.cn/problem/P1048），測評結果為“Accepted”。 

【例2】背包問題

問題描述

有N件物品和一個容量為M的背包。第i件物品的重量是Wi，價值是Di。求解將哪些物品裝入背包可使這些物品的重量總和不超過背包容量，且價值總和最大。

輸入

第一行：物品個數N （1≤N≤3,402）和背包大小M（1≤M≤12,880）。

第二行至第 N+1 行：第i 個物品的重量 Wi（1≤Wi≤400）和價值Di（1≤Di≤100）。

輸出

輸出一行最大價值。

輸入樣例

4 6

1 4

2 6

3 12

2 7

輸出樣例

23

        （1）編程思路。

        最基本的0/1背包問題，可以按前面介紹的模板寫成一維數組的方式，也可以寫成二維數組的方式。

        （2）採用一維數組編寫的源程式1。

#include <stdio.h>
int max(int a,int b)
{
    if (a>b) return a;
    else return b;
}
int main()
{
    int f[12881]={0};
    int n,m;
    scanf("%d%d",&n,&m);
    int c[3500],w[3500];
    int i,j;
    for (i=1;i<=n;i++)
    {
        scanf("%d%d",&c[i],&w[i]);
    }
    for (i=1;i<=n;i++)
        for (j=m;j>=c[i];j--)
        {
           f[j]=max(f[j],f[j-c[i]]+w[i]);
        }
    printf("%d\n",f[m]);
    return 0;
}

         將上面的源程式1提交給洛谷題庫P2871 [USACO07DEC]Charm Bracelet S（https://www.luogu.com.cn/problem/P2871），測評結果為“Accepted”。

        （3）採用二維數組編寫的源程式2。

#include <stdio.h>
int max(int a,int b)
{
    if (a>b) return a;
    else return b;
}
int f[3410][12881]={0};
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int d[3410],w[3410];
    int i,j;
    for (i=1;i<=n;i++)
    {
        scanf("%d%d",&w[i],&d[i]);
    }
    for (i=1;i<=n;i++)       // 對每件物品進行處理
        for (j=1;j<=m;j++)
        {
           if (j-w[i]<0)
              f[i][j]=f[i-1][j];
           else
           {
               f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+d[i]);
           }
        }
    printf("%d\n",f[n][m]);
    return 0;
}

        將上面的源程式2提交給洛谷題庫P2871 [USACO07DEC]Charm Bracelet S（https://www.luogu.com.cn/problem/P2871），測評結果為“Unaccepted”，其中測試點#2和測試點#10，顯示“MLE”。 

【例3】裝箱問題

題目描述

有一個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30，每個物品有一個體積（正整數）。

要求n個物品中，任取若幹個裝入箱內，使箱子的剩餘空間為最小。

輸入格式

1個整數，表示箱子容量

1個整數，表示有n個物品

接下來n行，分別表示這n個物品的各自體積。

輸出格式

1個整數，表示箱子剩餘空間。

輸入樣例

24

6

8

3

12

7

9

7

輸出樣例

0

        （1）編程思路1。

        本題也是典型的0/1背包問題，並且是0/1背包的簡化版，把箱子看成背包，容量看成載重量，每個物品的體積看成重量，剩餘空間最小也就是儘量裝滿背包。於是這個問題便成了：

        有一個載重量為V的背包，有N個物品，儘量多裝物品，使背包儘量的重。

        定義數組f[20001]，其中元素f[i]表示重量i可否構成。

        狀態轉移方程為： f[j]=f[j-w[i]]   { f[j-w[i]]=true}

        初始時，f[0]=1，什麼也不裝，重量0肯定可以構成。其餘元素全部為0。

        最終的解就是v-x （x<=n 且f[x]=true 且 f[x+1..n]=false）。

        （2）源程式1。

#include <stdio.h>
int main()
{
    int f[20001]={0};
    int v,n;
    scanf("%d%d",&v,&n);
    int w[31];
    int i,j;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    f[0]=1;
    for (i=1;i<=n;i++)
        for (j=v;j>=w[i];j--)
        {
           if (f[j-w[i]]==1)
              f[j]=1;
        }
    for (i=v;i>0;i--)
        if (f[i]==1) break;
    printf("%d\n",v-i);
    return 0;
}

         （3）編程思路2。

        也可以這樣解決問題。

        定義數組f[20001]，其中元素f[j]表示載重量為j的背包可裝載的最大重量。

        顯然對於每個物品i而言，

        要麼不裝，f[j]=f[j]，

        要麼裝，  f[j]=f[j-w[i]]+w[i]

        取二者的較大值。

        因此，狀態轉移方程為：f[j]=max(f[j],f[j-w[i]]+w[i]) 

        這個狀態轉移方程可以這樣理解：要載重為j的背包空出w[i]（j-w[i]）的空間且裝上第i個物品，比不裝獲得的價值大時，就裝上它。

        初始時，數組f的元素值全部為0。各背包全部為空。

       最終的解就是v-f[v]。

      （4）源程式2。

#include <stdio.h>
int max(int a,int b)
{
    if (a>b) return a;
    else return b;
}
int main()
{
    int f[20001]={0};
    int v,n;
    scanf("%d%d",&v,&n);
    int w[31];
    int i,j;
    for (i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    for (i=1;i<=n;i++)
        for (j=v;j>=w[i];j--)
        {
           f[j]=max(f[j],f[j-w[i]]+w[i]);
        }
    printf("%d\n",v-f[v]);
    return 0;
}

        將上面的源程式提交給洛谷題庫P1049 [NOIP2001 普及組] 裝箱問題（https://www.luogu.com.cn/problem/P1049），測評結果為“Accepted”。

【例4】數字組合

問題描述

有n個正整數，找出其中和為t（t也是正整數）的可能的組合方式。如：

n=5，5個數分別為1,2,3,4,5，t=5；

那麼可能的組合有5=1+4和5=2+3和5=5三種組合方式。

輸入

輸入的第一行是兩個正整數n和t，用空格隔開，其中1<=n<=20，表示正整數的個數，t為要求的和（1<=t<=1000）

接下來的一行是n個正整數，用空格隔開。

輸出

和為t的不同的組合方式的數目。

輸入樣例

5 5

1 2 3 4 5

輸出樣例

3

        （1）編程思路。

         將輸入的和值t看成背包的總容量，輸入的每個正整數看成一件物品，其重量就是正整數本身，就是一個簡單的0/1背包問題。

        設f[i]表示構成和值i的不同組合方式的數目，初始時，f[0]=1（背包中什麼正整數沒放，肯定是0，和值0肯定有1種組合方式），其餘元素全部為0。

        顯然，對於正整數a，如果加入背包，則有f[j]=f[j]+f[j-a]。

       （2）源程式。

#include <stdio.h>
#include <string.h>
int main()
{
    int n,t;
    scanf("%d%d",&n,&t);
    int i,j;
    int f[1005]={0};
    f[0]=1;
    for (i=1;i<=n;++i)
    {
        int a;
        scanf("%d",&a);
        for (j=t;j>=a;j--)
            f[j]+=f[j-a];
    }
    printf("%d\n",f[t]);
    return 0;
}

【例5】積木城堡

題目描述

XC的兒子小XC最喜歡玩的游戲用積木壘漂亮的城堡。城堡是用一些立方體的積木壘成的，城堡的每一層是一塊積木。小XC是一個比他爸爸XC還聰明的孩子，他發現壘城堡的時候，如果下麵的積木比上面的積木大，那麼城堡便不容易倒。所以他在壘城堡的時候總是遵循這樣的規則。

小XC想把自己壘的城堡送給幼兒園裡漂亮的女孩子們，這樣可以增加他的好感度。為了公平起見，他決定把送給每個女孩子一樣高的城堡，這樣可以避免女孩子們為了獲得更漂亮的城堡而引起爭執。可是他發現自己在壘城堡的時候並沒有預先考慮到這一點。所以他現在要改造城堡。由於他沒有多餘的積木了，他靈機一動，想出了一個巧妙的改造方案。他決定從每一個城堡中挪去一些積木，使得最終每座城堡都一樣高。為了使他的城堡更雄偉，他覺得應該使最後的城堡都儘可能的高。

任務：

請你幫助小XC編一個程式，根據他壘的所有城堡的信息，決定應該移去哪些積木才能獲得最佳的效果。

輸入

第一行是一個整數N（N<=100），表示一共有N座城堡。以下N行每行是一系列非負整數，用一個空格分隔，按從下往上的順序依次給出一座城堡中所有積木的棱長。用-1結束。一座城堡中的積木不超過100塊，每塊積木的棱長不超過100。

輸出

一個整數，表示最後城堡的最大可能的高度。如果找不到合適的方案，則輸出0。

輸入樣例

2

2 1 –1

3 2 1 -1

輸出樣例

3

         （1）編程思路。

        塔好積木再拿走就相當於當初搭的時候沒選拿走的積木。這樣一轉化，問題就清楚了。把積木可搭建的最大高度看成背包的載重，每塊積木的高度就是物品的重量。也就是用給定的物品裝指定的包，使每個包裝的物品一樣多，且在符合條件的前提下儘量多。

        這樣就變成典型的0/1背包問題了。對於每一個城堡求一次，最終找到每一個城堡都可達到的最大高度即可。

        定義二維數組int f[101][10001]，其中元素f[i][j]=1表示第i座城堡高度為j可搭出，f[i][j]=0表示第i座城堡高度為j不能搭出。

        狀態轉移方程為： f[i][j]=f[i][j-a[k]]   { f[i][j-a[k]]=true}  其中a[k]表示第i座城堡所用的第k塊積木的棱長。

        初始時，f[i][0]=1，每座城堡高度為0肯定可以搭出來。

        從所有城堡高度的最小值開始枚舉，若對於某一高度值h，所有的f[1][h]~f[n][h]均為1，則h就是最後城堡的最大可能的高度。

        （2）源程式。

#include <stdio.h>
int f[101][10001]={0};
int main(void)
{
    int n;
    scanf("%d",&n);
    int i,j,k;
    int a[101];
    int min=10001;
    for (i=1;i<=n;i++)
    {
        int cnt=1;
        int sum=0;
        int x;
        while (1)
        {
            scanf("%d",&x);
            if (x==-1) break;
            sum+=x;
            a[cnt++]=x;
        }
        if (min>sum) min=sum;
        f[i][0]=1;
        for (j=1;j<cnt;j++)
          for (k=sum;k>=a[j];k--)
          {
             if (f[i][k-a[j]]==1)
                f[i][k]=1;
          }
    }
    for (i=min;i>0;i--)
    {
        for (j=1;j<=n;j++)
            if (f[j][i]==0) break;
        if (j>n) break;
    }
    printf("%d\n",i);
    return 0;
}

        將上面的源程式提交給洛谷題庫P1504 積木城堡（https://www.luogu.com.cn/problem/P1504），測評結果為“Accepted”。

 【例6】湊零錢

問題描述

韓梅梅喜歡滿宇宙到處逛街。現在她逛到了一家火星店裡，發現這家店有個特別的規矩：你可以用任何星球的硬幣付錢，但是絕不找零，當然也不能欠債。韓梅梅手邊有 10000枚來自各個星球的硬幣，需要請你幫她盤算一下，是否可能精確湊出要付的款額。

輸入

輸入第一行給出兩個正整數：N（≤10000）是硬幣的總個數，M（≤100）是韓梅梅要付的款額。第二行給出 N 枚硬幣的正整數面值。數字間以空格分隔。

輸出

在一行中輸出硬幣的面值 V1≤V2≤⋯≤Vk，滿足條件 V1 +V2 +...+Vk =M。數字間以 1 個空格分隔，行首尾不得有多餘空格。若解不唯一，則輸出最小序列。若無解，則輸出 No Solution。

註：我們說序列{ A[1],A[2],⋯ }比{ B[1],B[2],⋯ }“小”，是指存在 k≥1 使得 A[i]=B[i] 對所有 i<k 成立，並且 A[k]<B[k]。

輸入樣例

8 9

5 9 8 7 2 3 4 1

輸出樣例

1 3 5

         （1）編程思路。

        將要付的款額M看成背包的總容量，將N枚物品的面值看成裝入背包中物品的重量，本題實際上就是看用這N枚硬幣能否裝滿容量為M的背包，若能裝滿，輸出字典序最小的裝載方案。

        定義數組int f[105]；其中f[i]表示容量為i的背包是否能裝滿，初始時f[0]=1（肯定存在背包中什麼不裝的方案），其餘f[i]全為0。

        顯然，若 f[j-a[i]]=1，容量為j-a[i]的背包可以裝滿，則加入面值為a[i]的硬幣後，容量為j的背包也可裝滿，即f[j]=1。

        為了記錄路徑，定義數組int path[10005][105];，該數組記錄當前狀態是由哪個狀態轉移過來的，初始值也全為0。

        若f[j-a[i]]=1，則一定可得到f[j]=1，則記錄f[i][j]=1，表示容量為j的背包是加入了面值為a[i]的硬幣。

        因為裝入的方案可能有多種，為了輸出字典序最小的方案，顯然應該用面值儘可能小的硬幣來裝。為此，將保存面值的數組a先按從大到小的順序排序，這樣進行0/1背包時，物品的加入是按面值大的先加入背包，面值小的後加入背包，這樣後面加入的更小的面值方案會覆蓋前面加入的面值較大的方案，從而實現輸出字典序最小的硬幣方案。

（2）源程式。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int cmp(int a,int b)
{
    return a>b;
}
int path[10005][105];
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    int f[105],a[10005];
    int i,j;
    for (i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memset(f,0,sizeof(f));
    memset(path,0,sizeof(path));
    f[0]=1;
    sort(a+1,a+n+1,cmp);
    for (i=1;i<=n;i++)
    {
        for (j=m;j>=a[i];j--)
        {
            if (f[j-a[i]]==1)
            {
                f[j]=1;
                path[i][j]=1;
            }
        }
    }
    if (f[m]>0)
    {
        i=n , j = m;
        int flag = 0;
        while (i>0 && j>=0)
        {
            if (path[i][j])     // 當前狀態可選
            {
                if (flag==0) { printf("%d",a[i]); flag = 1;}
                else
                    printf(" %d",a[i]);
                j -= a[i];
            }
            i--;
        }
        printf("\n");
    }
    else
        printf("No Solution\n");
    return 0;
}

【例7】烹調方案

題目描述

gw希望能在T時間內做出最美味的食物，可使用的食材一共有n件，每件食材有三個屬性，ai，bi和ci，如果在t時刻完成第i樣食材則得到ai-t*bi的美味指數，用第i件食材做飯要花去ci的時間。

眾所周知，gw的廚藝不怎麼樣，所以他需要你設計烹調方案使得美味指數最大。

輸入

第一行是兩個正整數T和n（1<=n<=50），表示控制時間和食材個數。

下麵一行n個整數，ai

下麵一行n個整數，bi

下麵一行n個整數，ci。所有數字均小於100,000

輸出

輸出最大美味指數

輸入樣例

74 1

502

2

47

輸出樣例

408

         （1）編程思路。

         一般的背包問題中，每個物品的重量和價值是固定的，因此物品的裝入順序對結果不產生影響。

        在本題中，因為每種食材的加工完成時刻t不同，其得到的美味指數不一樣，美味指數與時刻t存線上性的關係。因此，需要考慮每種食材的加工順序。

        考慮相鄰的兩個食材x,y。假設現在已經耗費p的時間，若先加工食材x，再加工y，得到的美味指數為：

            a[x]-(p+c[x])*b[x]+a[y]-(p+c[x]+c[y])*b[y]          （式①）

         若先加工食材x，再加工y，得到的美味指數為：

           a[y]-(p+c[y])*b[y]+a[x]-(p+c[y]+c[x])*b[x]          （式②）

         對這兩個式子化簡，得到①＞②的條件是 c[x]*b[y]<c[y]*b[x]。

         只要滿足上面這個條件，則對於食材對(x,y)，x在y之前進行加工得到的美味指數一定最大。

定義結構體數組

struct node

{

    long long a, b, c;

} m[51];

來保存輸入的各食材數據。

        將結構體數組按成員分量c/b從小到大的順序排列後，按數組中的順序依次加工食材（也就是依次加入背包），就是簡單的0/1背包問題了。

    （2）源程式。

#include <stdio.h>
long long max(long long a,long long b)
{
    return a>b?a:b;
}
struct node
{
    long long a, b, c;
};
int main()
{
    int t,n;
    scanf("%d%d",&t,&n);
    struct node m[51];
    int i,j;
    for (i = 1; i <= n; i++)
        scanf("%lld",&m[i].a);
    for (i = 1; i <= n; i++)
        scanf("%lld",&m[i].b);
    for (i = 1; i <= n; i++)
        scanf("%lld",&m[i].c);
    for (i=1;i<n;i++)
        for (j=1;j<=n-i;j++)
          if (m[j].c*m[j+1].b>m[j+1].c*m[j].b)
          {
             struct node temp;
             temp=m[j];  m[j]=m[j+1];  m[j+1]=temp;
          }
    long long f[100001]={0};
    long long ans=0;
    for (i = 1; i <= n; i++)
        for (j = t; j>= m[i].c; j--)
        {
            f[j] = max(f[j], f[j-m[i].c] + m[i].a - j*m[i].b);
            ans = max(f[j], ans);
        }
    printf("%lld\n",ans);
    return 0;
}

        將上面的源程式提交給洛谷題庫P1417 烹調方案（https://www.luogu.com.cn/problem/P1417），測評結果為“Accepted”。 

【例8】多米諾骨牌

問題描述

多米諾骨牌由上下2個方塊組成，每個方塊中有1∼6個點。現有排成行的上方塊中點數之和記為S1，下方塊中點數之和記為S2，它們的差為|S1-S2 |。

如圖，S1=6+1+1+1=9，S2=1+5+3+2=11， |S1-S2|=2。

每個多米諾骨牌可以旋轉180°，使得上下兩個方塊互換位置。請你計算最少旋轉多少次才能使多米諾骨牌上下2行點數之差達到最小。

對於圖中的例子，只要將最後一個多米諾骨牌旋轉180°，即可使上下2行點數之差為0。

輸入

輸入文件的第一行是一個正整數 n (1≤n≤1000)，表示多米諾骨牌數。接下來的n行表示n 個多米諾骨牌的點數。每行有兩個用空格隔開的正整數，表示多米諾骨牌上下方塊中的點數 a和b，且1≤a,b≤6。

輸出

輸出文件僅一行，包含一個整數。表示求得的最小旋轉次數。

輸入樣例

4

6 1

1 5

1 3

1 2

輸出樣例

1

         （1）編程思路。

         不管骨牌這樣旋轉變換，其上下兩行數字和s1+s2=sum，得到的總和sum是不會變的。

        題目要求的是上下兩行數字和最小差值情況下的最小交換次數。直接表示差值，可能有正有負，不太方便。我們可以轉化一下，保存某一行的數字和（例如上面的第1行的數字和S1），由於每次旋轉交換隻是把上下兩個數交換，所有骨牌上下兩行數的總和sum是不變的，這樣差值就容易求出來了，|sum-s1-s1|就是所求上下兩行數字和的差值了。

        設 f[i][j] 表示前i個數字，第一行的數字和是j時，最小的交換次數。初始值所有f[i][j]都是無窮大（本題中可以直接設置為300000，就足夠大了），f[1][a[1]]=0（第1張骨牌第1行的和值為自身，顯然不用交換），f[1][b[1]]=1（第1張骨牌第1行的和值為下麵的數字，需要旋轉180°，交換1次）。（數組a[]和b[]分別保存第一行和第二行各骨牌上面的數字）

         由於n張骨牌的點數和最大可能為6*n，因此可以將背包容量看成6*n。之後從第2張骨牌開始，每張骨牌加入背包中，考慮狀態轉移

if (j-a[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-a[i]]);    // 當前不交換

if (j-b[i] >= 0) f[i][j] = min(f[i][j], f[i-1][j-b[i]]+1);  // 當前交換

        最後再枚舉一下前n個骨牌第一行的和f[n][i]，找出使絕對值abs(sum-i-i)最小的f[n][i]就是所求的最小交換次數。

       （2）源程式。

#include <stdio.h>
int min(int a,int b)
{
    return a<b?a:b;
}
int abs(int a)
{
    return a>0?a:-a;
}
int a[1005],b[1005],f[1005][6005];
int main()
{
    int n;
    scanf("%d",&n);
    int i,j;
    int sum=0;
    for (i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        sum+=a[i]+b[i];
    }
    for (i=1;i<=n;i++)
        for (j=0;j<=6*n;j++)
            f[i][j]=300000;
    f[1][b[1]]=1;
    f[1][a[1]]=0;
    for (i=2;i<=n;i++)
    {
        <
您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • python面向對象之魔術方法(特定時機自動觸發) 魔術屬性
    魔術方法(特定時機自動觸發) __init__ 構造方法 觸發時機：實例化對象,初始化的時候觸發 功能：為對象添加成員 參數：參數不固定,至少一個self參數 返回值：無 # (1) 基本語法 class MyClass(): def __init__(self): print("構造方法被觸發 . ...
  • 結構型：四. 代理模式
    代理模式是什麼 代理模式是一種結構型設計模式， 讓你能提供真實服務對象的替代品給客戶端使用。 代理接收客戶端的請求併進行一些處理 （訪問控制和緩存等）， 然後再將請求傳遞給服務對象。 為什麼用代理模式 在某些情況下客戶類不想或者不能訪問目標對象，這時候就可以使用代理類訪問。 代理模式怎麼實現 pac ...
  • import 導入模塊或包
    import 導入模塊或包 文件就是一個模塊,文件夾就是一個包文件夾裡面可以有很多文件,就相當於包中有好多的模塊. import 模塊或者包(包是文件夾,模塊是文件)模塊不會被重覆導入，引入一次終生受益 '''調用的時候: 模塊.變數 模塊.函數 模塊.類''' (1) 模塊.變數 print(my ...
  • 數據結構：DHUOJ 單鏈表ADT模板應用演算法設計：長整數加法運算（使用單鏈表存儲計算結果）
    1.標題 //標題一共六個級別 # 一級標題 ## 二級標題 ### 三級標題 #### 四級標題 ##### 五級標題 ###### 六級標題 #一級標題 ##二級標題 ###三級標題 ####四級標題 #####五級標題 六級標題 2.字體 **粗體** *斜體* ***粗體加斜體*** ~~刪 ...
  • 序列化器 Serializer
    內容概要 序列化器介紹 Serializer的使用 基本使用（序列化） 欄位類型 欄位參數 序列化 定製序列化的欄位 反序列化 反序列化之新增 反序列化之修改 反序列化之局部和全局鉤子 ModelSerializer 模型類序列化器 ModelSerializer 額外添加參數 內容詳細 序列化器介 ...
  • 一個註解@Recover搞定醜陋的迴圈重試代碼
    在實際項目中其中一部分邏輯可能會因為調用了外部服務或者等待鎖等情況下出現不可預料的異常，在這個時候我們可能需要對調用這部分邏輯進行重試，代碼裡面主要就是使用for迴圈寫一大坨重試的邏輯，各種硬編碼，各種辣眼睛的補丁。 ...
  • 【Python】數據加密解密技術
    Python如何加密解密？感興趣的小伙伴可以舉一下腳，我看看有多少。咳咳咳，正式開始了，今天給大家分享的是Python如何加密解密，感興趣的小伙伴要認真學起來。 前言 加密演算法主要分為：哈希演算法、對稱加密演算法、非對稱加密演算法。 •哈希演算法：MD5、SHA256 •對稱加密演算法：DES、AES、CBC ...
  • 再見XShell，這款國人開源的終端命令行工具更nice！
    一、需求：創建一個HashMap集合，鍵是學號(String)，值是學生對象(Student),存儲三個鍵值對元素，並遍歷 分析： 1.定義學生類 2.創建HashMap集合對象 3.創建學生對象 4把學生添加到集合中 5.遍歷集合 public class StudentDemo { public ...
一周排行
    -Advertisement-
    Play Games
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類