让你们见识新世纪少年学C++编的是什么！！（经典编程问题：背包）

血戮魔动冰 · 发表于 2009-6-24 17:31:19

以下内容摘自网上：

P01: 01背包问题
题目
有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[v]=max{f[i-1][v],f[i-1][v-c]+w}。

这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c的背包中”，此时能获得的最大价值就是f [i-1][v-c]再加上通过放入第i件物品获得的价值w。

注意f[v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照这个方程递推完毕后，最终的答案并不一定是f[N] [V]，而是f[N][0..V]的最大值。如果将状态的定义中的“恰”字去掉，在转移方程中就要再加入一项f[v-1]，这样就可以保证f[N] [V]就是最后的答案。至于为什么这样就可以，由你自己来体会了。

优化空间复杂度
以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[0..V]的所有值。那么，如果只用一个数组f [0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[v]呢？f[v]是由f[i-1][v]和f[i-1] [v-c]两个子问题递推而来，能否保证在推f[v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v -c]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c]保存的是状态f[i -1][v-c]的值。伪代码如下：

for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c]+w};

其中的f[v]=max{f[v],f[v-c]}一句恰就相当于我们的转移方程f[v]=max{f[i-1][v],f[i- 1][v-c]}，因为现在的f[v-c]就相当于原来的f[i-1][v-c]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[v]由f[v-c]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

总结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/paradisemoon/archive/2009/05/29/4224763.aspx

代码：
[codes=C++]
#include <iostream>

using namespace std;

int main()
{
int N = 0, V = 0;
cin >> N >> V;
int * DP = new int [V+1];
int i = 0, j = 0;
int temp = 0, weight = 0;
for ( i = 0; i <= V; i++ )
{
      DP = 0;
}
for ( i = 0; i < N; i++ )
{
      scanf( "%d%d", &temp, &weight );
      for ( j = V; j >= temp; j-- )
      {
         if ( DP[j-temp] + weight > DP[j] )
         {
            DP[j] = DP[j-temp] + weight;
         }
      }
}
cout << DP[V];
system( "PAUSE" );
return 0;
}
[/codes]

白银の式神 · 发表于 2009-6-24 17:39:46

实际上就素比赛专用。

nikki · 发表于 2009-6-24 17:53:02

C++。。。
很多不懂

显示全部楼层 · 发表于 2009-6-24 17:56:25

提示: 作者被禁止或删除内容自动屏蔽

嗜血魂 · 发表于 2009-6-24 20:16:21

NOI

~~~~~~ [s:166]

未来的大叔 · 发表于 2009-6-24 21:04:15

路过

xiaojiao · 发表于 2009-6-24 21:47:17

看不懂

digimondm · 发表于 2009-6-25 11:07:52

这不就是背包问题嘛、、
在OI里是基础恩- -

aeris · 发表于 2009-6-25 11:45:45

scanf。。。怎么看都不像C++，C和C++还是有区别的。
贴个原汁原味的C++代码（摘自本人的的GMM）

template <
    template <
        typename _ContainerType,
        typename _ContainerAllocator
    > class _Container,
    typename _Allocator,
    typename _StringChar,
    typename _StringCharTraits,
    typename _StringAllocator
>
inline void string_advanced_split(
                                const std::basic_string<
                                    _StringChar,
                                    _StringCharTraits,
                                    _StringAllocator> &compoundString,
                                _Container<
                                    std::basic_string<
                                        _StringChar,
                                        _StringCharTraits,
                                        _StringAllocator
                                    >,
                                    _Allocator> &stringContainer,
                                _StringChar quote,
                                _StringChar delim
                                )
{
    typedef std::basic_string<_StringChar, _StringCharTraits, _StringAllocator> StringType;
    bool inQuotes = false;
    StringType chunkString;
    BOOST_FOREACH(_StringChar ch, compoundString)
    {
        if (inQuotes)
        {
            if (ch == quote)
            {
                inQuotes = false;
            }
            else
            {
                chunkString += ch;
            }
        }
        else
        {
            if (ch == delim)
            {
                stringContainer.push_back(chunkString);
                chunkString.clear();
            }
            else if (ch == quote)
            {
                inQuotes = true;
            }
            else
            {
                chunkString += ch;
            }
        }
    }
    stringContainer.push_back(chunkString);
}

复制代码

azrael · 发表于 2009-6-25 12:34:29

应该说c++可以兼容C吧
C、C++区别的确挺大的
变量的申明
面向对象（最大区别吧）
当然包括泛型
等~
纯属个人观点- -

digimondm · 发表于 2009-6-25 13:31:59

-。 -看到template< template<了，悲剧的VC6不支持ORZ。。

		自动登录	找回密码
密码			点一下

阿里山慝少该用户已被删除	发表于 2009-6-24 17:56:25 \| 显示全部楼层提示: 作者被禁止或删除内容自动屏蔽
阿里山慝少该用户已被删除
	回复使用道具举报 ???í?¨