目录

描述

应用

        简单背包

        题目描述

        输入格式

        输出格式

        数据范围

        输入样例

        输出样例

          代码实现

        多重背包问题

        题目描述

        输入格式

        输出格式

        数据范围

        输入样例

        输出样例

        代码实现

总结

---

描述

        背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？在编程中应用广泛，今天，我们就来看看背包问题该如何解决。

应用

        简单背包

        题目描述

                有N件物品和一个容量是V的背包，每件物品只能使用一次。

                第Ii件物品的体积是Vi，价值是Wi.

                求解将哪些物品装入背包，可以使这些物品的体积不超过背包总体积，且总价值最大。

        输入格式

                第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

                接下来有N行，每行两个证书Vi，Wi，用空格隔开，分别表示第i件物品的体积和价值。

        输出格式

                输出一个整数，表示最大价值。

        数据范围

                0<N,V<=1000

                0<vi,wi,<=1000

        输入样例

4 5

1 2

2 4

3 4

4 5

        输出样例

        

8

          代码实现

                我们可以用一个表示背包的二维数组 bp[ i ][ j ]来实现

                求出一件物品加或者不加入背包两者中的最优解。

#include<iostream>
using namespace std;
int n,V,v[1100],w[1100],dp[1100][1100];
int main()
{
	cin>>n>>V;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i]>>w[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=V;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j>=v[i])
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=V;i++)
	{
		ans=max(ans,dp[n][i]);
	}
	cout<<ans;
} 

        多重背包问题

        题目描述

                有N件物品和一个容量是V的背包，每件物品只能使用一次。

                第Ii件物品的体积是Vi，价值是Wi.

                求解将哪些物品装入背包，可以使这些物品的体积不超过背包总体积，且总价值最大。

        输入格式

                第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

                接下来有N行，每行两个证书Vi，Wi，Si，用空格隔开，分别表示第i件物品的体积，价值和数量。

        输出格式

                输出一个整数，表示最大价值。

        数据范围

                0<N<=1000

                0<V<=2000

                0<vi,wi,si<=2000

        输入样例

4 5

1 2 3

2 4 1

3 4 3

4 5 2

        输出样例

10

        代码实现

                本题考查了多重背包的二进制优化方法。

                我们使用二进制来表示si为si-2^k+1+2^k-1        

再用背包公式进行实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,V,v[114514],w[114514],dp[114514],tot;
signed main(){
	cin>>n>>V;
	for(int i=1;i<=n;i++){
		int vv,ww,ss;
		cin>>vv>>ww>>ss;//将si转换为2^1+2^2+2^3+……+2^(k-1)=(2^k)-1,si-(2^k)+1+(2^k)-1 
		int cnt=0,tmp=1;//cnt代表k 
		while(tmp<=ss){
			cnt++;
			tmp*=2;
		}
		cnt--;//使2^cnt=2^k-1<=si 
		for(int j=0;j<cnt;j++){
			tot++;
			v[tot]=(1<<j)*vv;
			w[tot]=(1<<j)*ww;
		}
		tot++;
		v[tot]=(ss-(1<<cnt)+1)*vv;//si-(2^k)+1
		w[tot]=(ss-(1<<cnt)+1)*ww;
	}
	for(int i=1;i<=tot;i++){
		for(int j=V;j>=0;j--){
			if(j>=v[i]){
				dp[j]=max(dp[j],dp[j-v[i]]+w[i]);//简化后的背包公式 
			}
		}
	}
	int ans=0;
	for(int i=0;i<=V;i++){
		ans=max(ans,dp[i]);
	}
	cout<<ans;
	return 0;
} 

总结

        背包公式在c++的运用是广泛的，我们要熟练地掌握并有效地使用出来。

        （欢迎各位大佬提出建议）