經典01背包問題

問題描述

一個旅行者有一個最多能裝M公斤的背包，現在有n件物品，它們的重量分别是W1,W2,…,Wn，它們的價值分别為C1, C2, …,Cn。 求旅行者能獲得最大總價值。

輸入格式

1. 第 1 行：兩個整數，M(背包容量，M<=200)和N(物品數量，N <=30);
2. 第 2 到 N+1行： 每行兩個整數 Wi，Ci，表示每個物品的重量和價值。

輸出格式

• 僅一行，一個數，表示最大總價值。

輸入樣例

10 4

2 1

3 3

4 5

7 9

輸出樣例

12

問題分析

01背包問題特點：

每種物品僅有一件，可以選擇放或不放。

說明：不放分為被動不放和主動不去放目前物品兩種情況

定義狀态

f[i][v]表示前i件物品(全部或部分)放入一個容量為v（0<=v<=M）的背包可以獲得的最大價值。

目前物品 i 有兩種可能性：

1. 包的容量（需依次枚舉1<=v<=M中的每個包容量狀态）比目前物品容量小，裝不下，此時的最優價值與前 i-1 個的最優價值是一樣的，即 f[i][v] = f[i-1][v]

2. 包的容量大于等于目前物品容量，可以選擇向包裡放入該物品，但未必能得到目前最優的價值f[i][v]。是以在放與不放該物品兩者之間選擇最優的一種政策。此時的不放為主動不放，前一種可能性裡的放不下屬于被動不放。

   即：f[i][v]=max{f[i-1][v], f[i-1][v-w[i]]+c[i]}

綜合分析 ，得到如下狀态轉移方程：

if(w[i] < =v) f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+c[i]]);😉

else f[i][v] =f[i-1][v];

經典背包問題解法一

// C++代碼
#include<iostream>
#include<algorithm>

using namespace std;
/*
部分背包問題屬于貪心
經典01背包問題多歸于動态規劃算法範疇 
*/ 
const int maxm=201, maxn=31;
int m,n;

int w[maxn],c[maxn];//w 重量，c 價值
int f[maxn][maxm];//dp[maxn][maxm] 

int main()
{
	cout<< "輸入物品的個數和背包的大小（容量或重量）"<<endl;
	cin>> n >> m;
	
	cout<<"輸入各個物品的重量和價值：" <<endl;
	for(int i=1; i<=n; i++)
	  cin>> w[i] >> c[i];
	  
	for(int i=1;i<=n;i++)
	  for(int v=m;v>0;v--)//包的容量依次從1到m枚舉遞推也可以
	  {
	  	if(w[i]<=v)//f[i][v]表示前i件物品，總重量不超過v的最優（大）價值 
	  	  f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
	  	else
	  	  f[i][v]=f[i-1][v];
	   } 
	
	cout<< f[n][m]<<endl;//f[n][m]即為結果，最優解 
	
	return 0;
 } 

           

經典背包優化空間解法二

#include<iostream>
#include<algorithm>

using namespace std;
/*
部分背包問題屬于貪心
經典01背包問題多歸于動态規劃算法範疇 
*/ 
const int maxm=201, maxn=31;
int m,n;

int w[maxn],c[maxn];//w 重量，c 價值
int dp[maxm];//dp[v]表示重量不超過v公斤的最大價值
             //如有n個物品，可分n個階段，用循環
			 // 第i個階段某個v狀态，是從第i-1個階段v狀态轉移過來的
			 //如價值大于前一階段的狀态，則更新目前狀态 ，否則不更新

int main()
{
	cout<< "輸入物品的個數和背包的大小（容量或重量）"<<endl;
	cin>> n >> m;
	
	cout<<"輸入各個物品的重量和價值：" <<endl;
	for(int i=1; i<=n; i++)
	  cin>> w[i] >> c[i];
	  
	for(int i=1;i<=n;i++)     //共進行n輪（階段）
	  for(int v=m;v>=w[i];v--)//必須逆序，否則前一階段比較小的V狀态會被覆寫，不能滿足記憶化需求
	                          //即需要從大V向小V依次求解 
	  {
	  	dp[v]=max(dp[v],dp[v-w[i]]+c[i]);

	   } 
	
	cout<< dp[m]<<endl;//dp[m]即為結果，最優解 
	
	return 0;
 } 

           

01背包填表表示

初始化邊界：dp[0][v] =dp[i][0]=0

dp[N][M] 即為旅行者背包能獲得的最大總價值。

i/v	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1
2	1	3	3	4	4	4	4	4	4
3	1	3	5	5	6	8	8	9	9
4	1	3	5	5	6	8	8	9	12