c++ - 带一维数组的动态编程 USACO 培训 : Subset Sums

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。您的程序必须计算答案，而不是从表格中查找。

输入格式如上所述，输入文件包含一行，其中包含一个表示 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];

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

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

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

输出使MaxSum/2的方法数，除以2排除对称变体([1,4]+[2,3]/[2,3]+[1,4])

self 思考的问题:为什么内循环是反方向的？