0-1背包問題

1. 0-1背包問題

0-1背包問題模型：

一個總容量V的背包和N件物品，每件物品都有其體積w,價值v；每個物品是否在背包中即0-1情況，故稱該種問題為0-1背包問題。要求背包能裝下價值盡可能多的物品，求最大價值；

狀态描述：dp[i][j]表示第i件物品對于目前占用容量為j的價值狀态，其中1<=i<=n,0<=j<=V;

狀态分析：第i件物品是否加入背包，

                （1）加入，dp[i][j]等于dp[i-1][j-w]+v，第i-1件相對于j-wi的占容最大價值的最大價值加第i件價值；

                  (2)   沒加入，d[i][j]等于dp[i-1][j],即與第i-1件到j占容的最大價值；

 狀态轉換：

轉換結果：dp[N][V],第N件物品到占容為V的最大價值狀态

測試資料：

70 3

71 100

69 1

1 2

狀态分析表如下所示：

i \ j	1	2	...	68	69	70
1	...
2	...	0+1	0+1
3	2	0+2	...	2	0+2	1+2

 Code:

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int V,N;//V為容量，N為個數
vector<int> dpcol(1000,0);
vector<vector<int>> dp(100,dpcol);//N<=100,V<=1000
struct goods{
	int w;//權重或表示為占容
	int v;//價值value
};
vector<goods> goods(100,{0,0});
int main(){
	int w,v;
	while(cin>>V>>N){
		for(int i=1;i<=N;i++){
			cin>>w>>v;
			goods[i]={w,v};
		}//輸入物品
		for(int j=1;j<=V;j++){//0件物品的所有價值為0
			dp[0][j]=0;
		}//初始化第0件狀态
		for(int i=1;i<=N;i++){//物品V
			for(int j=V;j>=goods[i].w;j--){//倒序，由上一輪資料更新，能放入i物品
				dp[i][j]=max(dp[i-1][j-goods[i].w]+goods[i].v,dp[i-1][j]);
			}
			for(int j=goods[i].w-1;j>=0;j--){//不能放入i物品，照抄上一輪到j的價值,且//保證了dp[i][0]=0;
				dp[i][j]=dp[i-1][j];
			}
		}
		cout<<dp[N][V]<<endl;
	}
	return 0;
}
/**
70 3
71 100
69 1
1 2

3
 */
           

優化Code：

1.dp隻受上一輪結果影響，故将二維dp[i][j]一維話dp[j]。

2.for(V....goods[i].w) dp[j],未加入i物品時暫存上一輪dp,省略了二維的抄作業行為。

#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
int V,N;
int w,v;
vector<int> dp(101,0);
struct goods{
	int w,v;
};
vector<goods> goods(101,{0,0});
int main(){
	while(cin>>V>>N){
		for(int i=1;i<=N;i++){
			cin>>w>>v;
			goods[i]={w,v};
		}
		for(int j=0;j<V;j++){
			dp[j]=0;
		}
		for(int i=1;i<=N;i++){
			for(int j=V;j>=goods[i].w;j--){
				dp[j]=max(dp[j],dp[j-goods[i].w]+goods[i].v);
			}
		}
		cout<<dp[V]<<endl;
	}
	return 0;
}