圖解四種常見背包問題及優(yōu)化方式-創(chuàng)新互聯

背包分類

每件/種物品體積Vi
不超過背包容量的總價值大化W（不一定裝滿）

創(chuàng)新互聯-專業(yè)網站定制、快速模板網站建設、高性價比沛縣網站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式沛縣網站制作公司更省心,省錢,快速模板網站建設找我們，業(yè)務覆蓋沛縣地區(qū)。費用合理售后完善，十年實體公司更值得信賴。

01 背包：每件物品最多只用一次
完全背包：每件物品無限個
多重背包：每件物品有限ai個
分組背包：從每組選擇一個

01背包與動態(tài)規(guī)劃思路在這里插入圖片描述

代碼實現（二維樸素法）

在這里插入圖片描述

#include#include
using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];//默認初始為0
int dp[N][N];

int main() {	cin >>n >>m;
	for (int i = 1; i<=n; i++) cin >>v[i] >>w[i];

	for(int i = 1; i<=n; i++) 
		for(int j = 0; j<=m; j++) {	dp[i][j] = dp[i-1][j];
			if(j>=v[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-v[i]] + w[i]);
		}
	cout<

代碼實現（滾動數組，轉態(tài)壓縮）
#include#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int dp[N];

int main() {cin>>n>>m;
	for (int i = 1; i<= n; i++) cin>>v[i]>>w[i];
	
	for(int i = 1; i<= n; i++)
	    for(int j = m; j >= v[i]; j--) {	//這里空集部分判斷直接挪到循環(huán)里面
	    	//不用推導，直接繼承上一層
	    	dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
		}
	cout<
完全背包與數列推導優(yōu)化
最樸素的思路起點
代碼實現（顯然會超時，1000三次方過億次了，C++的 1s 大體運行一億次）
#include#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N][N];

int main() {cin >>n >>m;
    for(int i = 1; i<= n; i++) cin >>v[i] >>w[i];
    
    for(int i = 1; i<= n; i++) 
       for(int j = 0; j<= m; j++) 
          for(int k = 0; k*v[i]<= j; k++)
              f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
    cout<< f[n][m]<
DP常見的數列推導優(yōu)化推導遞推公式，常減去一項來觀察規(guī)律實現降維。
#include#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N][N];

int main() {cin >>n >>m;
    for(int i = 1; i<= n; i++) cin >>v[i] >>w[i];
    
    for(int i = 1; i<= n; i++) 
       for(int j = 0; j<= m; j++) {   f[i][j] = f[i-1][j];
           if(j >= v[i]) f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);
       }
           
    cout<< f[n][m]<
狀態(tài)壓縮區(qū)分 01背包(全上層) 和 完全背包(本層+上層) 的遍歷順序。
#include#include

using namespace std;

const int N = 1010;

int n,m;
int v[N],w[N];
int f[N];

int main() {cin >>n >>m;
    for(int i = 1; i<= n; i++) cin >>v[i] >>w[i];
    
    for(int i = 1; i<= n; i++) 
       for(int j = v[i]; j<= m; j++) {   f[j] = max(f[j],f[j-v[i]]+w[i]);
       }
           
    cout<< f[m]<
多重背包與二進制枚舉優(yōu)化
最樸素的思路起點（如果數據過大和完全背包一樣超時）
#include#include

using namespace std;

const int N = 110;

int n,m;
int v[N],w[N],s[N];
int f[N][N];

int main() {cin >>n >>m;
    for(int i = 1; i<= n; i++) cin >>v[i] >>w[i] >>s[i];
    
    for(int i = 1; i<= n; i++)
       for(int j = 0; j<= m; j++) 
          for(int k = 0; k*v[i]<= j && k<= s[i]; k++) {  f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
          }
    cout<< f[n][m]<
二進制枚舉優(yōu)化比如要枚舉0->1023中所有的數能不能湊成其中任意一個數
我們平常的枚舉方法就是：0,1,2,3,4,5,…,1023。這樣枚舉1024次
使用二進制枚舉優(yōu)化，就可以只需枚舉10次就可以枚舉出任意一個數。
將0~1023這1024個數分為10個組，
每組分別是：1 2 4 8 16 32 64 128 256 512 這10個數字(2^0 2^1 2^2 … 2^9)。
在枚舉的時候只枚舉這10個數字，選或不選。就可以枚舉出0~1023中的任意一個數字




二進制枚舉優(yōu)化代碼實現
#include#include

using namespace std;

const int N = 25000;

int n,m;
int v[N],w[N];
int f[N];

int main() {cin >>n >>m;
    int cnt = 0;
    for (int i = 1; i<= n; i++) {int a,b,s;
        cin >>a >>b >>s;
        int k = 1;
        while(k<= s) {cnt++;
            v[cnt] = a*k;
            w[cnt] = b*k;
            s -= k;
            k *= 2;
        }
        if(s >0) {cnt++;
            v[cnt] = a*s;
            w[cnt] = b*s;
        }
    }
    n = cnt;
    for(int i = 1; i<= n; i++) 
       for(int j = m; j >= v[i]; j--)
          f[j] = max(f[j],f[j-v[i]] + w[i]);
          
    cout<< f[m]<< endl;
    return 0;
}
分組背包與狀態(tài)壓縮總結
和01背包特別像，不過多一個組內選擇
狀態(tài)壓縮以及遍歷順序的總結只要是上一層推導的，則從后往前
如果是同層推導的，則從前往后
只要是由上層某個方向定向推來的，就可以進行狀態(tài)壓縮
代碼實現#include#include

using namespace std;

const int N = 110;

int v[N][N],w[N][N],s[N];
int f[N];
int n,m;

int main() {cin >>n >>m;
    for(int i = 1; i<= n; i++) {cin >>s[i];
        for(int j = 1; j<= s[i]; j++) {cin >>v[i][j] >>w[i][j];
        }
    }
    
    for(int i = 1; i<= n; i++) 
       for(int j = m; j >= 0; j--)
           for(int k = 1; k<= s[i]; k++)
              if(j >= v[i][k]) f[j] = max(f[j],f[j-v[i][k]]+w[i][k]);
    cout<< f[m]<< endl;
    return 0;
}
                
     你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧
            

            網頁題目：圖解四種常見背包問題及優(yōu)化方式-創(chuàng)新互聯            

            地址分享：http://weahome.cn/article/pedss.html