在解决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。样本输出(文件子集4
经过大量阅读后,我发现了一种算法,该算法被解释为 0/1 knapsack问题的变体。我用代码实现了它,并解决了问题。但是,我不知道我的代码是如何工作的或正在发生的事情。
*主要问题:我想知道有人可以向我解释背包算法如何工作,以及我的程序如何在我的代码中实现?
我的代码:
#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;
}
*注意:只是要强调,此代码确实有效,我只是想解释它为什么工作。谢谢:)
我想知道为什么许多来源无法帮助您。
用我的丑陋英语再尝试一次:
方式[0] = 1;
有一种单一的方法来制作空总和
num*(num 1))/2
这是maxsum-范围1..num
中所有数字的总和(算术进展之和)
if((((num*(num 1))/2)%2 == 1)
没有机会将奇数分为两个相等的部分
for(int i = 1; i&lt; = num; i )
范围中的每个数字
for(int j =(num*(num 1))/2 -i; j> = 0; - j) 方法[J I] =方法[J];
SUM j + i
可以使用SUM j
和具有值i
的项目构建。
例如,考虑您要使总和15.
在外部周期的第一步中,您使用的是数字1,并且有ways[14]
变体可以制作此总和。
在外部周期的第二步中,您使用的是数字2,并且有ways[13]
新的变体可以添加这些新变体。
在外部周期的第三步中,您使用的是数字3,并且有ways[12]
新的变体来制作此和,您必须添加这些新变体。
方式[(num*(num 1))/2/2]/2
输出制作maxsum/2的方法的输出数量,然后除以两个以排除对称变体([1,4] [2,3]/[2,3]/[2,3] [1,4])
自我思考的问题:为什么内部周期朝反向方向?