快捷導(dǎo)航

C語言背包問題求解全過程(貪心方法)

更新時(shí)間：2024年06月13日 09:12:25 作者：渙清。

背包問題是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃問題,而貪心算法是一種常用的解決背包問題的方法,這篇文章主要給大家介紹了關(guān)于C語言背包問題求解(貪心方法)的相關(guān)資料,文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下

問題描述：

有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?cè)萘俊?/li>
物品：A B C D E F G
重量：35 30 60 50 40 10 25
價(jià)值：10 40 30 50 35 40 30

算法描述：

貪心算法（又稱貪婪算法）是指，在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。

貪心算法不是對所有問題都能得到整體最優(yōu)解，關(guān)鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個(gè)狀態(tài)以前的過程不會(huì)影響以后的狀態(tài)，只與當(dāng)前狀態(tài)有關(guān)。

問題分析：

1.目標(biāo)函數(shù)： ∑pi最大，使得裝入背包中的所有物品pi的價(jià)值加起來最大。

2.約束條件：裝入的物品總重量不超過背包容量：∑wi<=M( M=150)

3.貪心策略：選擇單位重量價(jià)值最大的物品

算法設(shè)計(jì)：

計(jì)算出每個(gè)物品單位重量的價(jià)值
按單位價(jià)值從大到小將物品排序
根據(jù)背包當(dāng)前所剩容量選取物品
如果背包的容量大于當(dāng)前物品的重量，那么就將當(dāng)前物品裝進(jìn)去。否則，那么就將當(dāng)前物品分割再裝進(jìn)去，然后跳出循環(huán)結(jié)束。

代碼實(shí)現(xiàn)：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000;
float z[maxn];
 
void Sort(int n,float w[],float v[]){
	for(int i=0;i<n;i++)
		z[i]=v[i]/w[i];//用z[]存物品的單位重量價(jià)值 
	for(int i=0;i<n;i++){//此排序的策略是每次把單位重量物品的價(jià)值最大的物品放在前面 
		for(int j=i+1;j<n;j++){
			if(z[i]<z[j]){
				float temp = z[i];
				z[i] = z[j];
				z[j]=temp;
				float tempw = w[i];
				w[i] = w[j];
				w[j] = tempw;
				float tempv = v[i];
				v[i] = v[j];
				v[j] = tempv; 
			}
		}
	}
}
 
void fire(int n,float w[],float v[],float x[],float pimax){
	Sort(n,w,v);//根據(jù)單位重量物品的價(jià)值對物品進(jìn)行排序 
	int i;
	for(i=0;i<n;i++){
		if(w[i]>pimax)	break;
		x[i] = 1;	//x[]數(shù)組用來記錄此次是否選擇物品，1代表全部拿走，0代表不拿，小數(shù)代表部分拿 
		pimax -= w[i];
	}
	if(i<=n-1)  x[i] = pimax/w[i]; 
} 
 
 
int main(){
	int n;
	float pi=0; 
	float pimax,v[maxn],w[maxn],x[maxn];//w[],每個(gè)物品的重量,v[]代表每個(gè)物品的價(jià)值,pimax代表最大容量 
	memset(x,0,sizeof(x));
	cout<<"請輸入最大容量：";
	cin>>pimax;
	cout<<"請輸入物品(物品可以任意分割)數(shù)量：";
	cin>>n;
	cout<<"請輸入每個(gè)物品的重量和價(jià)值："<<endl;
	for(int i=0;i<n;i++){
		cin>>w[i]>>v[i];
	}
	fire(n,w,v,x,pimax);
	for(int i=0;i<n;i++){
		if(x[i]==1){
			pi+=v[i];
		}
		else{
			pi+=v[i]*x[i];
		}
	}
	cout<<"最終收獲的物品(物品可以任意分割)價(jià)值為："<<pi<<endl;
	return 0;
}

運(yùn)行結(jié)果：