当前位置：首页 > article >正文

趣味算法------多重背包问题

article 2024/11/13 15:38:35

编辑

前言

例题

解题思路

具体代码

优化和注意事项

前言

多重背包问题是组合优化问题的一种，它是经典背包问题的扩展。在多重背包问题中，每种物品都有一个固定的数量限制，即可以被选择放入背包的次数是有限的。问题的目标是在背包容量限制下，选择物品组合以最大化总价值。多重背包问题可以通过动态规划算法解决，但由于物品数量的限制，其状态转移方程和时间复杂度可能会比标准的0-1背包问题复杂。在实际应用中，多重背包问题的解决方案可以通过二进制优化等技术来提高效率.

这篇算法是根据上一章01背包问题算法优化而来:

趣味算法------单一背包问题（01背包问题）贪心算法解决-CSDN博客

例题

题目描述
有 N 件物品和一个容量是 V 的背包。每件物品可以多次选用。
第 i 件物品的体积是 vi ，价值是 wi 。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

输入输出格式
输入格式
第一行两个整数N,V,用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
一个非负整数，代表结果。

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

输入输出样例2
输入
1 2
2 2
输出
2

解题思路

初始化：代码首先读取背包的容量（V）和物品的数量（N），并初始化一个二维数组 lst 作为动态规划表，以及两个一维数组 weights 和 values 来存储物品的重量和价值。
读取输入：代码接着读取每个物品的重量和价值，并存储在 weights 和 values 数组中。
状态转移方程：动态规划表 lst 的状态转移方程是根据经典的0-1背包问题的状态转移方程进行修改的。对于每个物品 i 和背包容量 j，状态转移方程考虑了两种情况：不包含当前物品 i 的最大价值（lst[i - 1][j]）和包含当前物品 i 的最大价值（lst[i - 1][j - weights[i - 1]] + values[i - 1]）。如果当前物品的重量小于或等于背包容量，就选择这两种情况中的较大者作为 lst[i][j] 的值。
填充动态规划表：代码通过两个嵌套循环来填充动态规划表 lst。外层循环遍历物品，内层循环遍历背包容量。在每次迭代中，根据状态转移方程更新 lst[i][j] 的值。
输出结果：最后，代码输出动态规划表中的最终值 lst[N][V]，这是在背包容量限制下可以获得的最大价值。

具体代码


#include<stdio.h>
#include<stdlib.h>
#define maxlen 100
int main(void)
{
	int N, V;
	scanf("%d%d", &N, &V);
	int lst[maxlen][maxlen] = { 0 };
	int* weights = (int*)malloc(N * (sizeof(N)));
	int* values = (int*)malloc(N * (sizeof(N)));
	for (int i = 0; i < N; i++)
	{
		int w, v;
		scanf("%d%d", &w, &v);
		weights[i] = w;
		values[i] = v;
	}
	for(int i = 1;i<=N;i++)
		for (int j = 0; j <= V; j++)
		{
			if (j < weights[i - 1])
				lst[i][j] = lst[i - 1][j];
			else
			{
				int num1 = lst[i - 1][j];
				int num2 = lst[i][j - weights[i - 1]] + values[i - 1];
				if (num1 > num2)
					lst[i][j] = num1;
				else
					lst[i][j] = num2;
			}
		}
	printf("%d", lst[N][V]);
	return 0;
}