中央論壇 - CENTER BBS

標題: 0-1 knapsack [打印本頁]

---

作者: wc_big_pig天尊    時間: 2008-2-17 17:25
標題: 0-1 knapsack
#include <iostream>
using namespace std;


#define LIMIT 46
#define KIND 5


struct Item
{
    int v;
    int w;
    int num;
};


int main()
{
    Item item[KIND] =
    {
        {19,  5, 6},
        {24,  6, 6},
        {33,  8, 5},
        {45, 11, 1},
        {50, 12, 1}
    };
      
   
    int table[LIMIT][KIND]={0};
    int value[LIMIT]={0};
   
   
    for(int i=1; i<LIMIT; i++)
    {

        value = value[i-1];
        
        for(int k=0; k<KIND; k++)
            table[k] = table[i-1][k];

        
        for(int j=0; j<KIND; j++)
        {
            bool putable = (item[j].w <= i);
            bool selectable = (item[j].num > table[i-item[j].w][j]);
            
            if(putable && selectable)
            {
                if( value < value[i-item[j].w] + item[j].v ){
                    value = value[i-item[j].w] + item[j].v ;
                    
                    for(int k=0; k<KIND; k++)
                        table[k] = table[i-item[j].w][k];
                    
                    table[j]++;
                }
            }
        }
    }
   
   
    for(int m=1; m<LIMIT; m++)
    {
        cout << value[m] << "\t";
        for(int n=0; n<KIND; n++)
        {
            cout << table[m][n] << "\t";
        }
        cout << endl;
    }
   
    return 0;
}

---

歡迎光臨 中央論壇 - CENTER BBS (https://mail.centerbbs.com/)

Powered by Discuz! X3