c c++ 01背包问题动态规划解决

01背包问题解决方法不少，动态规划是其中之一，动态规划的问题解题思路都差不多（一些浅见），基本要素是最优子结构性质，子问题重叠性质，自底向上的求解方法。只要了解了基本要素，那么这种题型也会更好理解。本题有不少注释，便于读者阅读。">01背包问题解决方法不少，动态规划是其中之一，动态规划的问题解题思路都差不多（一些浅见），基本要素是最优子结构性质，子问题重叠性质，自底向上的求解方法。只要了解了基本要素，那么这种题型也会更好理解。本题? [更多]

#include
#include

int C[200][200];//前i个物品装入容量为j的背包中获得的最大价值

int max（int aint b）  //返回较大值
{
    if（a >= b）
        return a;
    else return b;
}

int KnapSack（int nint w[]int v[]int x[]int W）  //物体个数n 物品重量w[]物品价值v[]，物品选择状态x[]背包容量W
{
    int ij;
    //接下来四行是初始左上角为0
    for（i = 0; i <= n; i++）
        C[i][0] = 0;
    for（j = 0; j <= W; j++）
        C[0][j] = 0;

    for（i = 0; i <= n - 1; i++） //选择货物
    {
        for（j = 0; j <= W; j++） //选择容量
        {
            if（j < w[i]）
                C[i][j] = C[i - 1][j];
            else
                C[i][j] = max（C[i - 1][j] C[i - 1][j - w[i]] + v[i]）;
        }
    }

    j = W;  //令j初始为容量
    for（i = n - 1; i >= 0; i--）  //找回最优解过程
    {
        if（C[i][j] > C[i - 1][j]）  //比

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      79506  2013-11-05 16:47  KnapSack\bin\Debug\KnapSack.exe

     文件       1059  2013-11-05 16:10  KnapSack\KnapSack.cbp

     文件        242  2013-11-05 16:47  KnapSack\KnapSack.layout

     文件       2182  2013-11-05 16:47  KnapSack\main.cpp

     文件       4789  2013-11-05 16:47  KnapSack\obj\Debug\main.o

     目录          0  2013-11-05 16:48  KnapSack\bin\Debug

     目录          0  2013-11-05 16:48  KnapSack\obj\Debug

     目录          0  2013-11-05 16:48  KnapSack\bin

     目录          0  2013-11-05 16:48  KnapSack\obj

     目录          0  2013-11-05 16:48  KnapSack

----------- ---------  ---------- -----  ----

                87778                    10