带一维数组 USACO 培训的动态规划：子集和

Question

在解决 USACO 培训问题时，我发现了动态规划。处理这个概念的第一个训练问题是一个称为子集和的问题。

问题陈述如下：

对于从 1 到 N (1 <= N <= 39) 的许多连续整数集，可以将集合分成两个总和相同的集合。例如，如果 N=3，可以用一种方式划分集合 {1, 2, 3} 使得两个子集的总和相同：

{3} 和 {1,2}

这算作单个分区（即，颠倒顺序算作相同分区，因此不会增加分区数）。如果N=7，则有四种方式对集合{1, 2, 3, ... 7}进行分区，使得每个分区的总和相同：

{1,6,7} 和 {2,3,4,5}

{2,5,7} 和 {1,3,4,6}

{3,4,7} 和 {1,2,5,6}

{1,2,4,7} 和 {3,5,6}

给定 N，你的程序应该打印包含从 1 到 N 的整数的集合可以分成两个总和相同的集合的方法数。如果没有这样的方式，则打印 0。您的程序必须计算答案，而不是从 table 中查找答案。

输入格式如上所述，输入文件包含一行，其中包含一个表示 N 的整数。

样本输入（文件subset.in） 7

输出格式输出文件包含一行和一个整数，表示可以从集合 {1, 2, ..., N} 中创建多少个相同和的分区。如果无法创建相同和的分区，则输出文件应包含 0。示例输出（文件 subset.out） 4

经过大量阅读，我发现了一种算法，该算法被解释为 0/1 背包问题 的变体。我在我的代码中实现了它，我解决了这个问题。但是，我不知道我的代码如何工作或发生了什么。

*主要问题：我想知道是否有人可以向我解释背包算法的工作原理，以及我的程序如何在我的代码中实现它？

我的代码：

 #include <iostream>
 #include <fstream>
 using namespace std;
 int main()
 {
      ifstream fin("subset.in");
      ofstream fout("subset.out");
      long long num=0, ways[800]={0};
      ways[0]=1;
      cin >> num;

      if(((num*(num+1))/2)%2 == 1)
      {
           fout << "0" << endl;
           return 0;
      }
      //THIS IS THE BLOCK OF CODE THAT IS SUPPOSED TO BE DERIVED FROM THE 
      //   O/1 KNAPSACK PROBLEM
      for (int i = 1; i <= num; i++) 
      {
           for (int j = (num*(num+1))/2 - i; j >= 0; --j) 
           {
                ways[j + i] += ways[j];
           }
      }
      fout << ways[(num*(num+1))/2/2]/2 << endl;
      return 0;
 }

*注意：只是强调一下，这段代码确实有效，我只是想解释一下为什么它有效。谢谢:)

Answer 1

我想知道为什么很多资源都无法帮助您。

用我丑陋的英语再试一次：

ways[0]=1;

只有一种方法可以生成空总和

num*(num+1))/2

这是 MaxSum - 1..num 范围内所有数字的总和（等差级数的总和）

if(((num*(num+1))/2)%2 == 1)

没有机会将奇数分成两等份

for (int i = 1; i <= num; i++)

对于范围内的每个数字

for (int j = (num*(num+1))/2 - i; j >= 0; --j) ways[j + i] += ways[j];

总和 j + i 可以使用总和 j 和值为 i 的项目构建。

例如，假设您要求和 15。
在外循环的第一步，您使用的是数字 1，并且有 ways[14] 个变体来计算这个总和。
在外循环的第二步，你使用的是数字 2，并且有 ways[13] new 个变体来计算这个和，你必须添加这些新变体。
在外循环的第三步，你使用的是数字 3，并且有 ways[12] new 变体来计算这个和，你必须添加这些新变体。

ways[(num*(num+1))/2/2]/2

输出方式数MaxSum/2，除以二排除对称变体（[1,4]+[2,3]/[2,3]+[1,4]）

自我思考的问题：为什么内循环是反方向的？

带一维数组 USACO 培训的动态规划：子集和

Dynamic Programming w/ 1D array USACO Training: Subset Sums

c++

algorithm

dynamic

knapsack-problem