上次演算法，講到很多這類型的問題。

遇到有點難度的問題，通常可往窮舉法方向思考，暴力演算法就是那樣非常直覺。

 

剛好看到網路有個範例，就瞭解一下。

 

背包問題（Knapsack Problem）

背包問題是關於最佳化的問題，要解最佳化問題可以使用「動態規劃」（Dynamic programming），從空集合開始，每增加一個元素就先求出該階段的最佳解，直到所有的元素加入至集合中，最後得到的就是最佳解。

背包問題.bmp 

 

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
using namespace std ;

/*
背包問題（Knapsack Problem）

背包問題是關於最佳化的問題，
要解最佳化問題可以使用「動態規劃」（Dynamic programming），
從空集合開始，每增加一個元素就先求出該階段的最佳解，
直到所有的元素加入至集合中，最後得到的就是最佳解。


*/
 
class body
{    
 private:
   
 public:
      char name[20];    
      int size;    
      int price;
};

typedef class body object;
 
int main(void)
{    
  const int LIMIT = 8;   // 重量限制
  const int N = 5;      // 物品種類
  const int MIN = 1;    // 最小重量
 
  int item[LIMIT+1] = {0};    
  int value[LIMIT+1] = {0};    
  int newvalue, i, s, p;    
  object a[] =
  {
   {"李子", 4, 4500},                  
   {"蘋果", 5, 5700},                  
   {"橘子", 2, 2250},                  
   {"草莓", 1, 1100},                  
   {"甜瓜", 6, 6700}
  };
 
/* 
  for(i = 0; i < N ;i++)
  {
    cout<<"物件"<<i+1<<"名稱:";
    cin>>a[i].name;
    cout<<"物件"<<i+1<<"重量:";
    cin>>a[i].size; 
    cout<<"物件"<<i+1<<"價值:";
    cin>>a[i].price;    
  }
*/
  cout<<endl;
  printf("物品\tkg\t價格\n");
  for(i = 0; i < 5 ;i++)
  {
    printf("%s\t%d\t%d\n", a[i].name, a[i].size, a[i].price);    
  }
 
  cout<<endl;
 
  cout<<"有一個背包最多可負重8kg,"<<endl;
  cout<<"今天有上表幾項物品可選擇,"<<endl;
  cout<<"在背包能承受的重量限制之下,"<<endl;
  cout<<"請你挑選出總價值最高的組合,"<<endl;
  cout<<"請問該組合總值多少?"<<endl<<endl;
 
 
     
  for(i = 0; i < N; i++)
  {        
   for(s = a[i].size; s <= LIMIT; s++)
   {            
     p = s - a[i].size;            
     newvalue = value[p] + a[i].price;            
     if(newvalue > value[s])// 找到階段最佳解 
     {               
      value[s] = newvalue;
      item[s] = i;             
     }        
   }    
  }
  cout<<"負重 ";
  for(i = 0; i <= 8 ;i++)
    cout<<setw(2)<<i<<"     ";   
  cout<<endl;
  cout<<"value";
  for(i = 0; i <= 8 ;i++)
    cout<<setw(2)<<value[i]<<"   ";
  cout<<endl;
  cout<<"item ";
  for(i = 0; i <= 8 ;i++)
    cout<<setw(2)<<item[i]<<"     "; 
  
 
  cout<<endl<<endl;
   
  printf("物品\t價格\n");    
      
  for(i = LIMIT; i >= MIN; i = i - a[item[i]].size)
  {        
   printf("%s\t%d\n",a[item[i]].name, a[item[i]].price);    
  }    
      
  printf("合計\t%d\n", value[LIMIT]);
 
  cout<<endl<<endl;
 
  system("pause");    
  return 0;
} 

 

 

 

arrow
arrow
    全站熱搜

    LawlietMoon 發表在 痞客邦 留言(2) 人氣()

    E-mail轉寄