• 算法-动态规划（背包）

    NO.1 01背包问题

    题目：

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

    第 i 件物品的体积是 vi，价值是 wi。

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

    输入格式

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

    接下来有 N  行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。

    输出格式

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

    数据范围

    0

    输入样例
    1. 4 5
    2. 1 2
    3. 2 4
    4. 3 4
    5. 4 5
    输出样例：
    8

    代码：（体积逆序）

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. using namespace std;
    14. typedef pair<int,int> PII;
    15. const int N = 1e3 + 10;
    16. int x,y;
    17. int v[N],w[N];
    18. int dp[int(1e3 + 10)];
    19. int main(){
    20. 	cin >> x >> y;
    21. 	for(int i = 1;i <= x;i ++){
    22. 		cin >> v[i] >> w[i];
    23. 	}
    24. 	int ans = 0;
    25. 	for(int i = 1;i <= x;i ++){
    26. 		for(int j = y;j >= v[i];j --){
    27. 			dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    28. 			//ans = max(ans,dp[j]);
    29. 		}	
    30. 	}
    31. 	for(int i = 0;i <= y;i ++){
    32. 		ans = max(ans,dp[i]);
    33. 	}
    34. 	cout << ans << endl;
    35. 	return 0;
    36. }

    NO.2 完全背包问题

    题目

    有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。

    第 i 种物品的体积是 vi，价值是 wi。

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

    输入格式

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

    接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

    输出格式

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

    数据范围

    0

    输入样例
    1. 4 5
    2. 1 2
    3. 2 4
    4. 3 4
    5. 4 5
    输出样例：
    10

    代码：（体积正序） 

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. using namespace std;
    14. typedef pair<int,int> PII;
    15. const int N = 1e3 + 10;
    16. int x,y;
    17. int v[N],w[N],dp[N];
    18. int main(){
    19. 	cin >> x >> y;
    20. 	for(int i = 1;i <= x;i ++)
    21. 		cin >> v[i] >> w[i];
    22. 	int ans = 0;
    23. 	for(int i = 1;i <= x;i ++){
    24. 		for(int j = v[i];j <= y;j ++){
    25. 			dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    26. 			ans = max(ans,dp[j]);
    27. 		}
    28. 	}
    29. 	
    30. 	cout << ans << endl;
    31. 	return 0;
    32. }

     NO.3 多重背包问题1

    题目

    有 N 种物品和一个容量是 V 的背包。

    第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

    求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
    输出最大价值。

    输入格式

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

    接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

    输出格式

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

    数据范围

    0

    输入样例
    1. 4 5
    2. 1 2 3
    3. 2 4 1
    4. 3 4 3
    5. 4 5 2
    输出样例：
    10

    代码：（体积正序）

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. using namespace std;
    14. typedef pair<int,int> PII;
    15. const int N = 1e2 + 10;
    16. int x,y;
    17. int v[N],w[N],s[N];
    18. int dp[N][N];
    19. int main(){
    20. 	cin >> x >> y;
    21. 	for(int i = 1;i <= x;i ++)
    22. 		cin >> v[i] >> w[i] >> s[i];
    23. 	for(int i = 1;i <= x;i ++){
    24. 		for(int j = 0;j <= y;j ++){
    25. 			for(int k = 0;k <= s[i] && k*v[i] <= j ;k ++){
    26. 				dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
    27. 			}
    28. 		}
    29. 	}
    30. 	cout << dp[x][y] << endl;
    31. 	return 0;
    32. }

     NO.4 多重背包问题2（二进制优化）

    题目：

    有 N 种物品和一个容量是 V 的背包。

    第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi 。

    求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
    输出最大价值。

    输入格式

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

    接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

    输出格式

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

    数据范围

    0

    提示：

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

    输入样例
    1. 4 5
    2. 1 2 3
    3. 2 4 1
    4. 3 4 3
    5. 4 5 2
    输出样例：
    10

    代码：（体积逆序）

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. using namespace std;
    14. typedef pair<int,int> PII;
    15. const int N = 2e4 + 10;
    16. int x,y;
    17. int v[N],w[N],s[N];
    18. int dp[N];
    19. int main(){
    20. 	cin >> x >> y;
    21. 	int cnt = 0;
    22. 	for(int i = 1;i <= x;i ++){
    23. 		int k = 1;
    24. 		int N,W,S;
    25. 		cin >> N >> W >> S;
    26. 		while(k <= S){
    27. 			v[cnt] = N * k;
    28. 			w[cnt ++] = W * k;
    29. 			S -= k;
    30. 			k *= 2;
    31. 		}
    32. 		if(S > 0){
    33. 			v[cnt] = N * S;
    34. 			w[cnt ++] = W * S;
    35. 		}
    36. 	}
    37. 	for(int i = 0;i < cnt;i ++){
    38. 		for(int j = y;j >= v[i];j --)
    39. 			dp[j] = max(dp[j],dp[j-v[i]] + w[i]); 
    40. 	}
    41. 	cout << dp[y] << endl;
    42. 	return 0;
    43. }

    NO.5  分组背包问题

    有 N 组物品和一个容量是 V 的背包。

    每组物品有若干个，同一组内的物品最多只能选一个。
    每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

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

    输出最大价值。

    输入格式

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

    接下来有 N组数据：

    • 每组数据第一行有一个整数 Si，表示第 i个物品组的物品数量；
    • 每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j个物品的体积和价值；
    数据范围

    0

    输入样例
    1. 3 5
    2. 2
    3. 1 2
    4. 2 4
    5. 1
    6. 3 4
    7. 1
    8. 4 5
    输出样例：
    8

     代码：（体积逆序）

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. #include
    7. #include
    8. #include
    9. #include
    10. #include
    11. #include
    12. #include
    13. using namespace std;
    14. typedef pair<int,int> PII;
    15. const int N = 1e2 + 10;
    16. int x,y;
    17. int s[N];
    18. int v[N][N],w[N][N],dp[N];
    19. int main(){
    20. 	cin >> x >> y;
    21. 	for(int i = 1;i <= x;i ++){
    22. 		cin >> s[i];
    23. 		for(int j = 0;j < s[i];j ++)
    24. 			cin >> v[i][j] >> w[i][j];
    25. 	}
    26. 	for(int i = 1;i <= x;i ++)
    27. 		for(int j = y;j >= 0;j --)//体积
    28. 			for(int k = 0;k < s[i];k ++)
    29. 				if(v[i][k] <= j)
    30. 					dp[j] = max(dp[j],dp[j-v[i][k]]+w[i][k]);
    31. 	cout << dp[y] << endl;
    32. 	return 0;
    33. }

  • 相关阅读:
    什么是Jmeter?Jmeter使用的原理步骤是什么？
    Docker 日志
    ALL IN ONE最佳实践方案分享(从硬件到软件全覆盖）
    leetcode经典面试150题---6.旋转数组
    Linux环境变量详解
    uniapp微信小程序地图实现周边
    jvm实现的锁优化
    网络通信基础
    调用了这么久的JS方法是长在对象、类、值本身还是原型链上？
    DataGridView绑定数据更新
  • 原文地址：https://blog.csdn.net/weixin_72982195/article/details/136381687