nhờ mọi người xem giúp em code bài toán cái túi
đề bài là : một người cần theo một cái túi trọng lượng không quá b, có n đồ vật đem theo. Đồ vật thứ j có trọng lượng aj và giá trị sử dụng cj. hỏi người đó cần mang những đồ vật nào để giá trị sử dụng lớn nhất.
ý tưởng của e khi dùng thuật toán duyệt toàn bộ là liệt kê các xâu nhị phân độ dài n, ứng với mỗi xâu nhị phân thì kiểm tra điều kiên trọng lượng, và sau đó tìm xâu nào có giá trị sử dụng lớn nhất
đây là code của e nhưng không biết sai chỗ nào, khi chạy chương trình thì mọi trường hợp nó đều tính ra là xâu nhị phân có n số 1 (111…1). mong mọi người giúp e sửa
#include<iostream>
#include<iomanip>
using namespace std;
int n,b,a[50],c[50],x[50],xmax[50],fmax=0;
void init();
bool check_weight();
void update();
void back_track(int i);
void result();
int main(){
init();
back_track(1);
result();
}
void init(){
cout<<"nhap so do vat n = ";
cin>>n;
cout<<"\nnhap trong luong toi da b = ";
cin>>b;
cout<<"\nnhap trong luong tung do vat ";
for (int i=1;i<=n;i++){
cin>>a[i];
}
cout<<"\nnhap gia tri tung do vat ";
for (int i=1;i<=n;i++){
cin>>c[i];
}
}
void update(){
int temp;
for (int i=1;i<=n;i++){
temp+=c[i]*x[i];
}
if (temp>fmax){
fmax=temp;
for (int i=1;i<=n;i++){
xmax[i]=x[i];
}
}
}
bool check_weight(){
int weight;
for (int i=1;i<=n;i++){
weight+=a[i]*x[i];
}
if (weight > b){
return false;
}
return true;
}
void back_track(int i){
for (int j=0;j<=1;j++){
x[i]=j;
}
if (i==n){
if(check_weight){
update();
}
}
else {
back_track(i+1);
}
}
void result(){
cout<<"gia tri su dung toi da = "<<fmax<<endl;
for (int i=1;i<=n;i++){
cout<<xmax[i]<<setw(2);
}
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?