Bài toán cái túi với thuật toán duyệt toàn bộ

mọi người có thể check giúp mình xem code của mình sai ở đâu dc không ạ.tks all

#include<iostream>
using namespace std;
int x[100]; int a[100]; int c[100];
int n,b;
int xopt[100];
int fopt;
void init();
bool check_weight();
void sum_up();
void back_track(int i);
void result();
void init(){
	cout<<"so do vat:";
	cin>>n;
	cout<<"trong luong toi da:";
	cin>>b;
	cout<<"trong luong tung do vat: ";
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	cout<<"gia tri tung do vat:";
	for (int i=1;i<=n; i++){
	    cin>>c[i];
	}
}
bool check_weight(){
	int weight=0;
	for (int i=1;i<=n;i++){
		weight+=a[i]*x[i];
	}
	
	if (weight>b){
		return false;
	}
	return true;
}
void sum_up(){
	int sum=0;
	for (int i=1;i<=n;i++){
		sum+=x[i]*c[i];
	}
	if(fopt<sum){
	   fopt=sum;
	for (int i=1;i<=n;i++){
		 xopt[i]=x[i];
	   }
	}
}
void back_track(int i){
	for (int j=0;j<=1;j++){
		x[i]=j;
		if (i==n){
			if (check_weight()){
			
				sum_up();
			}
		else back_track(i+1);	
		}
	}
}
void result(){
	cout<<"gia tri su dung toi uu:"<<fopt<<endl;
	for (int i=1;i<=n;i++){
		cout<<"phuong an toi uu"<<xopt[i]<<endl;
	}
}
int main() {

	init();
	back_track(1);
	result();
}

Cho xin cái đề bài đi bạn!

3 Likes

Một nhà thám hiểm cần đem theo một cái túi trọng lượng không quá 𝐵. Có 𝑁 đồ vật cần đem
theo. Đồ vật thứ 𝑖 có trọng lượng 𝑎𝑖, có giá trị sử dụng 𝑐𝑖 (𝑖 = 1, 2, . . . , 𝑁; 𝑎𝑖, 𝑐𝑖 ∈ 𝑍+). Hãy tìm cách đưa đồ vật vào túi cho nhà thám hiểm sao cho tổng giá trị sử dụng các đồ vật trong túi là lớn nhất.

đó bác ơi

Bài này thì cứ ưu tiên đồ vật nào có trọng lượng nhỏgiá trị lớn.
Tức là phải sắp xếp theo ưu tiên trên.

3 Likes

Chỗ này nè bạn hiền, bạn chú ý coi câu lệnh được đặt đúng chỗ chưa :kissing_smiling_eyes:

else back_track(i+1);
4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?