1.問題描述

有一個容量為V的背包，還有n個物體?，F(xiàn)在忽略物體實際幾何形狀，我們認(rèn)為只要背包的剩余容量大于等于物體體積，那就可以裝進(jìn)背包里。每個物體都有兩個屬性，即體積w和價值v。使物品裝入背包的價值大。

2.解決思路與分析

I．枚舉法，首先想到最簡單的枚舉法，通過列舉所有結(jié)果，從中篩選出滿足題意的結(jié)果。

II．回溯法，在枚舉法的基礎(chǔ)上進(jìn)行約束剪枝和限界剪枝。

III．動態(tài)規(guī)劃，運用動態(tài)規(guī)劃思想，動態(tài)規(guī)劃與分治法類似，都是把大問題拆分成小問題，通過尋找大問題與小問題的遞推關(guān)系，使用遞歸和遞推算法解決一個個小問題，最終達(dá)到解決原問題的效果。

如果裝不下當(dāng)前物品，那么前n個物品的最佳組合和前n-1個物品的最佳組合是一樣的。

如果裝得下當(dāng)前物品。
假設(shè)1?:裝當(dāng)前物品，在給當(dāng)前物品預(yù)留了相應(yīng)空間的情況下，前n-1個物品的最佳組合加上當(dāng)前物品的價值就是總價值。
假設(shè)2:不裝當(dāng)前物品，那么前n個物品的最佳組合和前n-1個物品的最佳組合是一樣
選取假設(shè)1和假設(shè)2中較大的價值，為當(dāng)前最佳組合的價值。

枚舉法代碼：

#include#include#includeconst int N=10;//全局變量，物品數(shù)量
const int bag=N;//全局變量，背包承重量
int max_value=0;//全局變量，記錄能獲得的大價值
int backpack(int a[],int v[],int w[],int n,int t)
{
	int max_v=0,max_w=0;//背包累積的大價值和大重量 
	if(t>n-1)//遞歸結(jié)束的條件 
	{
		printf("找到一個方案");
		for(int i=0;ibag)//根據(jù)max_w判斷該方案是否超重
			printf("\n該方案總價%d,總重%d，超重！不可行！??！\n",max_v,max_w);
		else{//如果不超重
			if(max_v>max_value)//比較該方案所獲得的價值是不是比全局最優(yōu)解更優(yōu)
				max_value=max_v;//更新最優(yōu)解
			printf("\n該方案總價%d,總重%d，可行\(zhòng)n",max_v,max_w);
		}
    }else{
        for(int i=1;i>=0;i--)//只取值1或0 
        {
            a[t]=i;//記錄當(dāng)前物品選1或不選0
			backpack(a,v,w,n,t+1);//遞歸到下一層
        }
    }
	return max_value;//返回大價值
}
int main()
{
	int a[N],v[N],w[N],i,start,end;
	printf("背包大承重%d公斤\n",bag);
	for(i=0;i

回溯法代碼：

#include#include#includeconst int N=10;//全局變量，物品數(shù)量
const int bag=N;//全局變量，背包承重量
int max_value=0;//全局變量，記錄能獲得的大價值
int count=0;//全局變量，用于記錄到達(dá)葉節(jié)點的次數(shù)
int a[N],v[N],w[N],r[N+1];//全局變量，分別保存0-1方案，物品價值，物品重量，剩余總價值
int backpack(int t,int now_v,int now_w)
{//t表示遞歸層數(shù)，now_v表示當(dāng)前層所累積的價值，now_w表示當(dāng)前層所累積的重量
	int i;
	if(t>N-1)//當(dāng)遞歸到達(dá)葉子節(jié)點時
	{
		printf("找到一個方案");
		for(i=0;ibag)//判斷方案是否超重
		{
			printf("\n該方案總價%d,總重%d，超重！不可行！??！\n",now_v,now_w);
		}
		else//如果不超重
		{
			if(now_v>max_value)//判斷該方案所獲得的價值是不是更優(yōu)
			{
				max_value=now_v;//更新最優(yōu)解
			}
			printf("\n該方案總價%d,總重%d，可行\(zhòng)n",now_v,now_w);
		}
		count++;
    }
    else
    {
        for(i=0;i<=1;i++)
        {
            a[t]=i;//記錄當(dāng)前物品選或不選
			now_v=now_v+v[t]*i;//根據(jù)0-1值累加價值
			now_w=now_w+w[t]*i;//根據(jù)0-1值累加重量
			if(now_w<=bag&&now_v+r[t+1]>max_value) // (限件減枝 約束減枝)
				backpack(t+1,now_v,now_w);//遞歸到下一層
        }
    }
	return max_value;//返回大價值
}
int main()
{
	int i,start,end;
	printf("背包大承重%d公斤\n",bag);
	for(i=0;i=0;i--)//計算所有情況下剩余物品的總價值(約束減枝)
	{
		r[i]=r[i+1]+v[i];
	}
	
	start=clock();
	printf("能獲得的大價值為：%d\n",backpack(0,0,0));
	end=clock();
	printf("檢查方案%d個,",count);
	printf("耗時:%dms\n",end-start);
	return 0;
}

動態(tài)規(guī)劃代碼：

#include#include#includeconst int N=1000;//全局變量，物品數(shù)量
const int bag=N;//全局變量，背包承重量
int max_value=0;//全局變量，記錄能獲得的大價值
int a[N],v[N],w[N],r[N+1];//全局變量，分別保存0-1方案，物品價值，物品重量，剩余總價值
int dp[N][bag+1]={0},fa[N]={0};
int max(int a,int b);
void Find(int N,int bag);
int backpack()
{
	for(int i=1;ij)
				dp[i][j]=dp[i-1][j];
			else
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
		}
		
	}
	return dp[N-1][bag];//返回大價值
}
void Find(int i,int j)
{
	if(i==0)
	{
		for(int i=0;ib) return a;
else return b;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧