1.問(wèn)題描述

有n個(gè)物體有重量和價(jià)值兩個(gè)屬性，一個(gè)能承重一定重量的背包。問(wèn)怎么選擇物體能實(shí)現(xiàn)背包里的價(jià)值最大化。

2.問(wèn)題具體化

假設(shè)有5個(gè)物體和一個(gè)背包。物體的重量分別是2、2、6、5、4，即w[]={0、2、2、6、5、4}，價(jià)值分別是6、3、5、4、6，即v[]={0、6、3、5、4、6}。背包承重為10。問(wèn)怎么選擇，能實(shí)現(xiàn)背包所背物體價(jià)值的最大化。

3. 解決過(guò)程

利用二維表格，通過(guò)自左向右、自下向上的計(jì)算，來(lái)繪制表格，左后再在表格的基礎(chǔ)上選擇最優(yōu)解。

• 3.1表格最后一行

  對(duì)最后一行的物體4來(lái)說(shuō)，只有兩種情況，要么裝入背包，要么不裝入。物體5的的重量是4。也就是說(shuō)在背包承重為0--3的時(shí)候物體5是裝不進(jìn)去的，所以背包為0，當(dāng)背包承重為4--10的時(shí)候，物體5可以裝進(jìn)去，又因?yàn)槲矬w5的價(jià)值為6，所以背包價(jià)值為6。

• 3.2表格倒數(shù)第二行

  表格倒數(shù)第二行的計(jì)算思路與倒數(shù)第一不一樣，因?yàn)槲覀円紤]背包里已經(jīng)有的物體。因?yàn)槲矬w4的重量為5。所以在背包承重為0--4的情況下即使空包也裝不進(jìn)去，所以不能裝入，包里原本是多少價(jià)值，就還是多少價(jià)值。在背包承重為5--8的時(shí)候，物體4可以裝進(jìn)去，但是物體5要拿出來(lái)才行，這樣的話背包的價(jià)值就變成4了，小于6。所以能然選擇不把物體4放進(jìn)去。在背包承重為9--10的時(shí)候，兩個(gè)都可以放進(jìn)去，所以背包的價(jià)值變成10了。

• 3.3最終計(jì)算出來(lái)的表格

  其他行的計(jì)算過(guò)程同上，最終結(jié)果如下。

• 3.4表格計(jì)算公式

  max( m(i+1,j) , m(i+1,j-wi)+vi )

• 3.5做出最優(yōu)選擇

  大體思想：我們從右上角（坐標(biāo)（1,10））開始，看（1,10）與（2,10）的值是不是一樣，一樣，則說(shuō)明物體1沒(méi)裝進(jìn)去，不一樣，則說(shuō)明物體1裝進(jìn)去了。
  void opt_way(int flag[],int w[], int table[num][weight])
  {
  int n = weight-1;
  for (size_t i = 0; i < num; i++)
  {

    if (table[i][n]==table[i+1][n])
    {
        flag[i] = 0;
    }
    else
    {
        flag[i] = 1;
        n = n - w[i+1];
    }

  }
  }

4.完整代碼

#include <iostream>
#define num 5
#define weight  11
using namespace std;

void init_table(int table[num][weight])
{
    for (size_t i = 0; i < num; i++)
    {
        for (size_t j = 0; j < weight; j++)
        {
            table[i][j] = 0;
        }
    }

}
void show_table(int table[num][weight])
{
    for (size_t i = 0; i < num; i++)
    {
        for (size_t j = 0; j < weight; j++)
        {
            cout <<table[i][j] << "\t";
        }
        cout << "\n";
    }

}
void creat_table(int table[num][weight],int w[],int v[])
{
    //給最后一行賦初值
    for (size_t i = 0; i < weight; i++)
    {
        if (w[num] > i)
            table[num - 1][i] = 0;
        else
        {
            table[num - 1][i] = v[num];
        }
    }
    //在最后一行基礎(chǔ)上給每行賦值
    for (int i = num - 1; i > 0; i--)
    {
        for (int j = 0; j < weight; j++)
        {
            if (w[i]>j)
            {
                table[i - 1][j] = table[i][j];
            }
            else if ((v[i] + table[i][j-w[i]])>table[i][j])
            {
                table[i-1][j] = v[i] + table[i ][j - w[i]];
            }
            else
            {
                table[i-1][j] = table[i][j];
            }
        }
    }

}



void opt_way(int flag[],int w[], int table[num][weight])
{
    int n = weight-1;
    for (size_t i = 0; i < num; i++)
    {
        if (table[i][n]==table[i+1][n])
        {
            flag[i] = 0;
        }
        else
        {
            flag[i] = 1;
            n = n - w[i+1];
        }
    }

}
int main()
{
    int w[num+1] = {0,2,2,6,5,4};
    int  v[num+1]= {0,6,3,5,4,6};
    int flag[num] = { 0, 0, 0, 0, 0 };
    int table[num][weight];
    init_table(table);
    creat_table(table,w,v);
    opt_way(flag,w,table);
    //----------------
    show_table(table);
    //------------------------------
    for (size_t i = 0; i < num; i++)
    {
        cout << flag[i];
    }
    getchar();
    return 0;
}

5.程序結(jié)果截圖

11001是最優(yōu)的選擇