首先，常见的背包分为7类（01背包，完全背包，多重背包，混合背包，二维费用背包，分组背包，依赖背包），这篇博客只写了前4种和01满背包（我太懒啦）

其实还有满背包，只不过可以应用到任何背包类型中，不是独立的背包类型

1.普通的01背包（最初的最初）

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

特点： 每种物品最多选一次

关键： 选或不选、逆序遍历、每件物品唯一

例题：简单背包问题 采药

2.完全背包

    memset(dp,0,sizeof(dp));
	for(int i=1;i<=V;i++) {
		for(int j=w[i];j<=N;j++) {
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<"max="<<dp[N];
}

特点： 每种物品无限件

关键： 无限取、正序遍历

例题：完全背包问题 砝码称重

3.多重背包

    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= 0; j--) {
            for (int k = 1; k <= s[i] && k * v[i] <= j; k++) {
                dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
            }
        }
    }
    cout << dp[V] << endl;

特点： 每种物品有限件（给定数量）

关键： 有限件、二进制优化、数量限制、拆分成01背包

例题：多重背包（1） 逃亡的准备

4.混合背包

 memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= N; i++) {
        int v, w, s;
        cin >> v >> w >> s;
        for (int j = V; j >= 0; j--) {
            for (int k = 1; k <= s && k * v <= j; k++) {
                dp[j] = max(dp[j], dp[j - k * v] + k * w);
            }
        }
    }
    cout << dp[V] << endl;

特点： 三种物品混合（01+完全+多重）

关键： 混合、分类处理、按类型选择遍历顺序

例题：【提高】混合背包 【例9.14】混合背包

5.01满背包

   memset(dp,-0x3f3f3f,sizeof(dp));//初始化为极小值
	dp[0]=0;
	for (int i=1; i<=N; i++) {
		int v,w;
		cin>>v>>w;
		for (int j=V; j>=v; j--) {
			dp[j]=max(dp[j],dp[j-v]+w);
		}
	}
	if (dp[V]<0)cout<<"No"<<endl;
	else cout<<dp[V]<<endl;

例题：01背包问题(满背包）（gfhd内0/69）