首页 文章

具有1D阵列的动态编程USACO训练：子集总和

提问于
浏览 次
0

在解决USACO培训问题时，我发现了动态编程 . 处理这个概念的第一个训练问题是一个叫做子集和的问题 .

The Problem Statement Follows ：

对于从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 . 你的程序必须计算答案，而不是从表中查找 .

INPUT FORMAT输入文件包含一行，其中一个整数表示N，如上所述 .

SAMPLE INPUT（文件subset.in）7

输出格式输出文件包含一行，其中包含一个整数，用于说明可以从集合{1,2，...，N}中生成多少个相同和的分区 . 如果没有方法可以生成相同和的分区，则输出文件应该包含0 . SAMPLE OUTPUT（文件subset.out）4

经过多次阅读，我发现了一种被解释为 0/1 knapsack problem 变体的算法 . 我在我的代码中实现了它，我解决了这个问题 . 但是，我不知道我的代码是如何工作的或者是怎么回事 .

*Main Question: I was wondering if someone could explain to me how the knapsack algorithm works, and how my program could possibly be implementing this in my code?

我的代码：

#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;
 }

*note: Just to emphasize, this code does work, I just would like an explanation why it works. Thanks :)

c++ algorithm dynamic knapsack-problem

1 回答

  • 1

    我想知道为什么众多消息来源无法帮助你 .

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

    方式[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 变体来做这个总和，你必须添加这些新的变种 .
    在外循环的第三步，你使用数字3，并且有 ways[12] new 变体来做这个总和，你必须添加这些新变种 .

    方式[（num *（num 1））/ 2/2] / 2

    输出MaxSum / 2的方法数，除以2以排除对称变量（[1,4] [2,3] / [2,3] [1,4]）

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

    回复于

相关问题