動態規劃解決部分和問題（java）

韓冰發布于2019-08-15 17:44 / 1772人閱讀

摘要：題目曉萌希望將到的連續整數組成的集合劃分成兩個子集合，且保證每個集合的數字和是相等。輸出包括一行，僅一個整數，曉萌可以劃分對應的集合的方案的個數。也就是本題可以轉化為部分和問題，即前個數的和能湊成的有多少種。注意的是和為一種。

題目：曉萌希望將1到N的連續整數組成的集合劃分成兩個子集合，且保證每個集合的數字和是相等。例如，對于N=3，對應的集合{1，2，3}能被劃分成{3} 和 {1,2}兩個子集合.

這兩個子集合中元素分別的和是相等的。

對于N=3，我們只有一種劃分方法，而對于N=7時，我們將有4種劃分的方案。

輸入包括一行，僅一個整數，表示N的值（1≤N≤39）。

輸出包括一行，僅一個整數，曉萌可以劃分對應N的集合的方案的個數。當沒發劃分時，輸出0。

樣例輸入

7
樣例輸出

分析：劃分成兩部分，那么這兩部分的值也就是可以確定的，值為N! / 2。

  所以N! 只有是偶數的話才可分。
  也就是本題可以轉化為部分和問題，即前N個數的和能湊成N! / 2的有多少種。
  注意的是 {1, 2} {3}和{3} {1, 2}為一種。
  設 dp[i][j]前i個數的部分和可以湊成j的子集數
  動態轉移方程：
  當j >= arr[i - 1]時 dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j]
  其他： dp[i][j] = dp[i - 1][j]

代碼實例：

        Scanner read = new Scanner(System.in);
        int N = read.nextInt();
        int sum = N * (N + 1)/ 2;
        if((sum & 1) == 1)// 如果和為奇數時  不可分
            System.out.println("0");
        else{
            // dp[i][j] 前i個數的部分和可以湊成j的子集數
            long[][] dp = new long[N +1][(sum / 2) + 1];
            //0可以湊成0
            dp[0][0] = 1;
            for(int i = 1; i <= N; ++i){
                for(int j = 0; j <= sum / 2; ++j){
                    if(j >= i){//當j >= arr[i - 1]時  dp[i][j] = dp[i - 1][j - arr[i - 1]] + dp[i - 1][j];
                        dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j];
                    }else{//其他： dp[i][j] = dp[i - 1][j];
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
            // 計數過程中類似的  {1, 2} {3}和{3} {1, 2} 會被重復記錄 所以除2
            System.out.println(dp[N][sum / 2] / 2);
        }

GPU云服務器云服務器 java動態規劃代碼 java零錢動態規劃租用idc機房解決的問題和帶來的效益動態規劃

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/69416.html

基本算法思想：遞歸+分治+動態規劃+貪心+回溯+分支限界

摘要：代碼實現見下面評論對應代碼動態規劃基本思想和分治法基本思想有共同的地方，不同的是子問題往往不是獨立的，有事母問題要借助子問題的解來判斷，因此把已經計算好的問題記錄在表格中，后續如果需要查詢一下，可以避免重復計算，這是動態規劃的基本思想。作者：心葉時間：2018-05-01 19:28 本文對應github地址：https://github.com/yelloxing/... 以上實現...

EscapedDog 2019-08-26 11:52 評論0 收藏0
Java面試 32個核心必考點完全解析

摘要：如問到是否使用某框架，實際是是問該框架的使用場景，有什么特點，和同類可框架對比一系列的問題。這兩個方向的區分點在于工作方向的側重點不同。 [TOC] 這是一份來自嗶哩嗶哩的Java面試Java面試 32個核心必考點完全解析（完）課程預習 1.1 課程內容分為三個模塊基礎模塊：技術崗位與面試計算機基礎 JVM原理多線程設計模式數據結構與算法應用模塊：常用工具集 ...

JiaXinYi 2019-08-16 16:53 評論0 收藏0
大廠算法面試之leetcode精講3.動態規劃

摘要：動態規劃問題一定會具備最優子結構，才能通過子問題的最值得到原問題的最值。另外，雖然動態規劃的核心思想就是窮舉求最值，但是問題可以千變萬化，窮舉所有可行解其實并不是一件容易的事，只有列出正確的狀態轉移方程才能正確地窮舉。大廠算法面試之leetcode精講3.動態規劃視頻教程（高效學習）:點擊學習目錄：1.開篇介...

番茄西紅柿 2021-11-22 14:56 評論0 收藏2637
動態規劃入門（以爬樓梯為例）

摘要：動態規劃算法通?；谝粋€遞推公式及一個或多個初始狀態。動態規劃有三個核心元素最優子結構邊界狀態轉移方程我們來看一到題目題目有一座高度是級臺階的樓梯，從下往上走，每跨一步只能向上級或者級臺階。概念動態規劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優化的數學方法。動態規劃算法通常基于一個遞推公式及一個或多個初始狀態...

cyixlq 2019-08-23 10:52 評論0 收藏0