Vua Tên Miền chuyên cung cấp tên miền đẹp, giá rẻ! Hãy liên hệ kỹ thuật: 0914205579 - Kinh doanh: 0912191357 để được tư vấn, hướng dẫn miễn phí, Cảm ơn quý khách đã ủng hộ trong thời gian qua!
kinh doanh, bán hàng, tư vấn, bảo hiểm Những cá nhân, tổ chức, đại lý,muốn bán, hợp đồng bảo hiểm
Wednesday, January 16, 2019

Bài toán cái túi (Knapsack Problem)

Bài này thực ra có 2 phiên bản : 
- Phiên bản 1 : là số đồ chọn là số nguyên.
ví dụ : 
có 3 món đồ với dung lượng túi là 10
+ món 1 : nặng 4 , giá trị 10
+ món 2 : nặng 6 , giá trị 10
+ món 3 : nặng 10, giá trị 21
Vì giá trị nguyên, nên dễ thấy ta phải chọn món thứ 3 để có giá trị là lớn nhất
- Phiên bản 2 : là tên trộm có thể cắt món đồ ra để được giá trị lớn nhất , cũng với ví dụ trên ta có giá trị 1 phần của từng món như sau :
10 / 4 = 2.5
10 / 6 = 1.666667
21 / 10 = 2.1
Tức là nếu theo cách này thì ta sẽ chọn món thứ nhất 4kg + 6kg ( của món thứ 3 ) thì sẽ được giá trị lớn nhất.
Code của bạn mình nghĩ là giải theo phương pháp tham lam nhưng cách đặt tên biến i,j.. nên đọc vào mệt lắm. Code này mình viết theo 2 phương pháp, mình giải phiên bản 1 bằng quy hoạch động và phiên bản 2 bằng tham lam :
-Giải thuật cho phương pháp tham lam rất đơn giản : sắp xếp lại các tỉ số giá trị ( cái mình vừa ví dụ ) sau đó thử sai là xong .
-Giải thuật cho QHD cũng đơn giản như sau : 
F[i][j] là giá trị lớn nhất có thể đạt được bao gồm i món đồ và giới hạn trọng lượng là j
thì ta có :
Không lấy món đồ đó thì thứ i thì : F[i][j] = F[i-1][j]
Ngược lại nếu chọn món đồ thứ i + điều kiện [được giá trị lớn hơn] thì
F[i][j] = F[i-1][j-khối lượng[i]] + giá trị[i]
Ta chỉ cần tính cho tới F[món đồ][giá tiền] nhập vào là xong 
Đây là code , có chỗ nào không hiểu thì mình sẽ giải thích :

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm> //sort function

using namespace std;


class Knapstack
{
public :

Knapstack(int number_of_items, int weight_of_bag);
~Knapstack();

//Copy constructor 
Knapstack::Knapstack(Knapstack &copy_object);
//overloading operator "=" 
const Knapstack &operator = (Knapstack &);

/*method for greedy*/
void Solving_by_greedy();
void Sort_items();

/*method for dynamic programming*/
void Solving_by_dynamic_programming();
void Dynamic_programming_trace_solution();

friend istream &operator >> (istream &, Knapstack &);

private :

int weight_of_bag;
int number_of_items; 

//data information
int *items_No;
int *items_value;
int *items_weight;
//solution array
float *greedy_solution;
int **dynamic_solution;
};


Knapstack::Knapstack(int number_of_items, int weight_of_bag)
:number_of_items(number_of_items), weight_of_bag(weight_of_bag)
{
greedy_solution = new float[number_of_items+1];
items_No = new int[number_of_items+1];
items_value = new int[number_of_items+1];
items_weight = new int[number_of_items+1];


dynamic_solution = new int *[number_of_items+1];
for(int x = 0; x <= number_of_items; x++)
{
dynamic_solution[x] = new int[weight_of_bag+1];
}

for(int x = 0; x <= number_of_items; x++)
{
*(items_No + x) = x+1;//fixed
*(items_value + x) = 0;
*(items_weight + x) = 0;
*(greedy_solution + x) = 0.0;
} 

for(int x = 0; x <= number_of_items; x++){
for(int y = 0; y <= weight_of_bag; y++){
dynamic_solution[x][y] = 0;
}
}
}


//Destructor 
Knapstack::~Knapstack()
{
delete[] items_No;
delete[] items_value;
delete[] items_weight;

delete[] greedy_solution;
for(int x = 0; x <= number_of_items; x++){
delete[] dynamic_solution[x];
}
delete[] dynamic_solution;
}


//Copy constructor
Knapstack::Knapstack(Knapstack &copy_object)
:number_of_items(copy_object.number_of_items), weight_of_bag(copy_object.weight_of_bag)
{
//For array of greedy algorithm
greedy_solution = new float[number_of_items+1];
items_No = new int[number_of_items+1];
items_value = new int[number_of_items+1];
items_weight = new int[number_of_items+1];

for(int x = 0; x <= number_of_items; x++)
{
*(items_No + x) = copy_object.items_No[x];
*(items_value + x) = copy_object.items_value[x];
*(items_weight + x) = copy_object.items_weight[x];
*(greedy_solution + x) = copy_object.greedy_solution[x];


//For array of dynamic programming algorithm
dynamic_solution = new int *[number_of_items+1];
for(int x = 0; x <= number_of_items; x++)
{
dynamic_solution[x] = new int[weight_of_bag+1];


for (int x = 0; x <= number_of_items; x++)
{
for (int y = 0; y <= weight_of_bag; y++)
{
dynamic_solution[x][y] = copy_object.dynamic_solution[x][y];
}
}



const Knapstack &Knapstack::operator = (Knapstack &obj)
{
if (&obj != this) //check for self-assignment
{
//deallocate new left-side of array
if((number_of_items != obj.number_of_items) || (weight_of_bag != obj.weight_of_bag))
{
//Reclaim space
delete[] items_No;
delete[] items_value;
delete[] items_weight;
delete[] greedy_solution;

for( int x = 0; x <= number_of_items; x++){
delete[] dynamic_solution[x];
}
delete[] dynamic_solution;
/*----END RECLAIM SPACE----*/

//Resize object.
number_of_items = obj.number_of_items;
weight_of_bag = obj.weight_of_bag;

//Create space for array copy
dynamic_solution = new int*[number_of_items+1];
for(int x = 0; x <= number_of_items; x++)
{
dynamic_solution[x] = new int[weight_of_bag+1];
}


items_No = new int[number_of_items+1];
items_value = new int[number_of_items+1];
items_weight = new int[number_of_items+1];
greedy_solution = new float[number_of_items+1];
/*----END CREATE SPACE----*/

//copy all arrays into object
for(int x = 0; x <= number_of_items; x++)
{
*(items_No + x) = obj.items_No[x];
*(items_value + x) = obj.items_value[x];
*(items_weight + x) = obj.items_weight[x];
*(greedy_solution + x) = obj.greedy_solution[x];
}

for (int x = 0; x <= number_of_items; x++)
{
for (int y = 0; y <= weight_of_bag; y++) 
{
dynamic_solution[x][y] = obj.dynamic_solution[x][y];
}
}
}
}
return *this; //reference return



istream &operator >> (istream &input, Knapstack &obj)
{
cout << "\n### Data Information ###\n";
cout << "\nThe number of items : ";
input >> obj.number_of_items;
cout << "\nThe maximum capacity of bags: ";
input >> obj.weight_of_bag;

for(int i = 1; i <= obj.number_of_items; i++)
{
cout << " The [" << i << "] item weigh : ";
input >> obj.items_weight[i];
cout << " Its value is : ";
input >> obj.items_value[i];
cout << endl;
}

return input;
}


void Knapstack::Sort_items()
{
for(int x = number_of_items; x >= 2; x--)
{
for(int y = 1; y <= number_of_items - x; y++)
{
if(((float)items_value[y]/items_weight[y]) > ((float)items_value[y-1]/items_weight[y-1]))
{
swap(items_weight[y], items_weight[y-1]);
swap(items_value[y], items_value[y-1]);
swap(items_No[y], items_No[y-1]);
}
}
}
}


void Knapstack::Solving_by_greedy() 
{
int _the;//the item
float max_profit = 0.0;

Sort_items();

for(_the = 1; _the < number_of_items; _the++)
{
if(items_weight[_the] > weight_of_bag)
break;

greedy_solution[_the] = 1.0;

weight_of_bag = weight_of_bag - items_weight[_the];
max_profit += items_value[_the];

cout << "\n Items chosen : "<< items_No[_the] 
<< "\nwith the % quantiy %:" << greedy_solution[_the] << endl;

}


if(_the <= number_of_items) 

greedy_solution[_the] = (float)weight_of_bag/items_weight[_the];
cout << "\n" << items_No[_the] << "\nwith the quantiy % chosen : " << greedy_solution[_the] << endl;
max_profit = max_profit + (greedy_solution[_the]*items_value[_the]);
}
cout << "\n Maximum value the thief can get : " << max_profit;
}


void Knapstack::Solving_by_dynamic_programming()
{
for (int x = 1; x <= number_of_items; x++)
{
for (int y = 0; y <= weight_of_bag; y++)
{
dynamic_solution[x][y] = dynamic_solution[x-1][y];
if (y >= items_weight[x] && dynamic_solution[x][y] < dynamic_solution[x-1][y-items_weight[x]] + items_value[x] && (y-items_weight[x]) >= 0)
{
dynamic_solution[x][y] = dynamic_solution[x-1][y-items_weight[x]] + items_value[x];
}
}
}
}

void Knapstack::Dynamic_programming_trace_solution()
{
cout << "Maximum value the thief can get : "
<< dynamic_solution[number_of_items][weight_of_bag] << endl;

while (number_of_items != 0)
{
if(dynamic_solution[number_of_items][weight_of_bag] != dynamic_solution[number_of_items-1][weight_of_bag])
{
cout << "Chosen items are : " << number_of_items;
weight_of_bag = weight_of_bag - items_weight[number_of_items];
}
number_of_items--;
}
}

void Menu()
{
Knapstack problem(10,10);
cin >> problem;

int command;
cout << "Enter a method for solving knapstack problems :\n\n"
<< "\n[1].Greedy\n" 
<< "\n[2].Dynamic programming\n" << endl;
cin >> command;


if (command == 1)
{
problem.Solving_by_greedy();
}
else
{
problem.Solving_by_dynamic_programming();
problem.Dynamic_programming_trace_solution();
}
}

int main()
{
Menu();
system("pause");
return 0;
}

Xếp lịch thi đấu vòng tròn 1 lượt

đăng 18:50, 11 thg 1, 2012 bởi Minh Nguyen   [ đã cập nhật 21:24, 7 thg 4, 2012 ]
Bài toán:
+ Xếp lịch thi đấu cho n cầu thủ thi đấu vòng tròn 1 lượt.
+ Mỗi cầu thủ phải đấu với các cầu thủ khác và mỗi cầu thủ chỉ phải đấu nhiều nhất 1 trận mỗi ngày.
+ Yêu  cầu là xếp lịch thi đấu sao cho số ngày thi đấu là ít nhất.

Giải thuật:

Bài toán tháp Hà Nội

đăng 18:43, 11 thg 1, 2012 bởi Minh Nguyen   [ đã cập nhật 01:33, 8 thg 4, 2012 ]
Mục đích của bài toán là thực hiện được yêu cầu của trò chơi. Dạng bài toán thông dụng nhất là: "Người chơi được cho ba cái cọc và một số đĩa có kích thước khác nhau có thể cho vào các cọc này. Ban đầu sắp xếp các đĩa theo trật tự kích thước vào một cọc sao cho đĩa nhỏ nhất nằm trên cùng, tức là tạo ra một dạng hình nón. Người chơi phải di chuyển toàn bộ số đĩa sang một cọc khác, tuân theo các quy tắc sau:
  • một lần chỉ được di chuyển một đĩa
  • một đĩa chỉ có thể được đặt lên một đĩa lớn hơn (không nhất thiết hai đĩa này phải có kích thước liền kề, tức là đĩa nhỏ nhất có thể nằm trên đĩa lớn nhất)".
Bài toán này có lời giải chính xác. Tuy nhiên các mở rộng cho trường hợp có nhiều hơn ba cọc cho đến nay vẫn chưa được giải cặn kẽ.
Đa số các trò chơi dạng này có 8 đĩa. Đối với người mới chơi thì có vẻ khó nhưng thật ra thuật giải của nó hết sức đơn giản:

[sửa]Thuật giải đệ quy

  • đặt tên các cọc là A, B, C -- những tên này có thể chuyển ở các bước khác nhau (ở đây: A = Cọc Nguồn, B = Cọc Đích, C = Cọc Trung Gian)
  • gọi n là tổng số đĩa
  • đánh số đĩa từ 1 (nhỏ nhất, trên cùng) đến n (lớn nhất, dưới cùng)
Để chuyển n đĩa từ cọc A sang cọc B thì cần:
  1. chuyển n-1 đĩa từ A sang C. Chỉ còn lại đĩa #n trên cọc A
  2. chuyển đĩa #n từ A sang B
  3. chuyển n-1 đĩa từ C sang B cho chúng nằm trên đĩa #n
Phương pháp trên được gọi là thuật giải đệ quy: để tiến hành bước 1 và 3, áp dụng lại thuật giải cho n-1. Toàn bộ quá trình là một số hữu hạn các bước, vì đến một lúc nào đó thuật giải sẽ áp dụng cho n = 1. Bước này chỉ đơn giản là chuyển một đĩa duy nhất từ cọc A sang cọc C.
Ngôn ngữ Pascal biểu diễn giải thuật trên là:
VAR n: Integer;
Procedure chuyen(sodia: Integer; CotNguon: Char; CotDich: Char; CotTG: Char);
   Begin
        If sodia>0 then begin
           chuyen(sodia-1, CotNguon, CotTG, CotDich);
           Writeln(CotNguon,'->',CotDich); { Dia lon nhat hien tai }
           chuyen(sodia-1, CotTG, CotDich, CotNguon)
        End;
   End;
BEGIN
     Write('Hay nhap so dia: '); Readln(n);
     chuyen(n,'A','C','B');//Thực hiện chuyển từ cột A sang cột C với cột B làm trung gian
     Readln;
END.
Ngôn ngữ C viết trên Dev C++
#include <cstdlib>
#include <iostream>
#include <conio.h>
 
using namespace std;
void chuyen(int sodia, char CotNguon, char CotDich, char CotTG)
{
        if (sodia>0)
        {
           chuyen(sodia-1, CotNguon, CotTG, CotDich);
           cout<<CotNguon<<"->"<<CotDich<<"\n";
           chuyen(sodia-1, CotTG, CotDich, CotNguon);
        }
}
int main()
{    char CotNguon,CotDich,CotTG;
    int n;
     cout<<"Hay nhap so dia: ";
     cin>>n;
     chuyen(n,'A','C','B');
     getch();
}

(Trên) Lời giải cho 3 đĩa. (Dưới) Lời giải cho 4 đĩa.
Tái tạo lại trang trong phần này để xem sự tương quan giữa hai lời giải.
Sau đây là dạng dễ xem hơn của thuật giải này:
  1. chuyển đĩa 1 sang cọc C
  2. chuyển đĩa 2 sang cọc B
  3. chuyển đĩa 1 từ C sang B sao cho nó nằm lên 2
Vậy ta hiện có 2 đĩa đã nằm trên cọc B, cọc C hiện thời trống
  1. chuyển đĩa 3 sang cọc C
  2. lặp lại 3 bước trên để chuyển 1 & 2 cho nằm lên 3
Mỗi lần dựng xong tháp từ đĩa i đến 1, chuyển đĩa i+1 từ cọc A là cọc xuất phát, rồi lại di chuyển tháp đã dựng lên đĩa i+1.
Theo Wiki
tcaviet@gmail.com

0 comments:

Post a Comment

domain, domain name, premium domain name for sales

Popular Posts