基础背包问题 - 多维有界背包问题 - 深度优先搜索 (递归)

缺乏、安全感 2023-02-17 03:28 2阅读 0赞

#  基础背包问题 - 多维有界背包问题 - 深度优先搜索 (递归) #

## 1. 基础背包问题 ##

背包问题 (Knapsack problem) 是一种组合优化的 NP 完全问题。给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价值最高。

如果限定每种物品只能选择 0 个或 1 个，则问题称为 **0-1 背包问题** (0-1 knapsack problem) 。  
如果限定物品 `j` 最多只能选择 `maxj` 个，则问题称为**有界背包问题** (bounded knapsack problem，BKP)。  
如果不限定每种物品的数量，每种物品都就可以选择任意多个，则问题称为**无界背包问题或完全背包问题** (unbounded knapsack problem，UKP)。

## 2. 多维有界背包问题 - 深度优先搜索 (递归) ##

现有 `N` 种 (`N` <= 100) 物品，每种物品都有体积  v i v\_i vi，重量  w i w\_i wi，数量  c i c\_i ci，价值  t i t\_i ti ( v i v\_i vi、 w i w\_i wi、 c i c\_i ci 和  t i t\_i ti 都为整数)。限制体积最多 `V` 立方厘米 (`V` <= 1000)，重量最多 `W` 公斤 (`W` <= 500)。如何选择物品，使得背包装过的物品总价值最大。

若 `V` 为 500，`W` 为 100，则选择物品的最大价值为 72 (72 = 10 \* 4 + 10 \* 2 + 4 \* 3：由 10 件物品 1，10 件物品 3 和 4 件物品 4 组成)。这是一个多维且有界的背包问题，属于常规 0-1 背包问题的扩展。

第一行测试用例个数。第二行，物品的种类 `N`，背包体积的限制 `V`，背包载重量的限制 `W`。

接下来 `N` 行，每行为该种物品i的体积  v i v\_i vi，重量  w i w\_i wi，数量  c i c\_i ci，价值  t i t\_i ti ( v i v\_i vi、 w i w\_i wi、 c i c\_i ci 和  t i t\_i ti 都为整数)。

`72` 选择物品子集所能获得的最大价值。

2
    5 500 100
    30 3 10 4
    50 8 10 5
    10 2 10 2
    23 5 8 3
    130 20 5 11
    5 500 100
    30 3 10 4
    50 8 10 5
    10 2 10 2
    23 5 8 3
    130 20 5 11

### 2.1 多维有界背包问题 - 深度优先搜索 (递归) ###

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    int computation = 0;
    
    void dfs_v1(int map[100][4], int N, int V, int W, int sumvolume, int sumvalue, int sumweight, int *max_value, int goods_class)
    {
    	if (sumvolume > V) {
    		computation++;
    		return;
    	}
    
    	if (sumweight > W) {
    		computation++;
    		return;
    	}
    
    	if ((sumvalue > *max_value))
    	{
    		*max_value = sumvalue;
    	}
    
    	if (goods_class >= N)
    	{
    		computation++;
    		return;
    	}
    
    	// volume - weight - number - value
    	// 选这类物品，然后选下一类
    	if (map[goods_class][2] > 0) {
    		map[goods_class][2] -= 1;
    		dfs_v1(map, N, V, W, sumvolume + map[goods_class][0], sumvalue + map[goods_class][3], sumweight + map[goods_class][1], max_value, goods_class + 1);
    		map[goods_class][2] += 1;
    	}
    
    	// 选这类物品，然后继续选择同类
    	if (map[goods_class][2] > 0) {
    		map[goods_class][2] -= 1;
    		dfs_v1(map, N, V, W, sumvolume + map[goods_class][0], sumvalue + map[goods_class][3], sumweight + map[goods_class][1], max_value, goods_class);
    		map[goods_class][2] += 1;
    	}
    
    	// 不选这类物品，然后选下一类
    	dfs_v1(map, N, V, W, sumvolume, sumvalue, sumweight, max_value, goods_class + 1);
    
    	return;
    }
    
    int inference(int map[100][4], int N, int V, int W)
    {
    	int ret = 0;
    	int max_value = INT_MIN;
    	int goods_class = 0;
    	int sumvolume = 0;
    	int sumvalue = 0;
    	int sumweight = 0;
    
    	dfs_v1(map, N, V, W, sumvolume, sumvalue, sumweight, &max_value, goods_class);
    
    	ret = max_value;
    
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int ret = 0;
    		int	N = 0, V = 0, W = 0;
    		int map[100][4] = { 0 };
    
    		computation = 0;
    
    		cin >> N >> V >> W;
    
    		for (int h = 0; h < N; h++)
    		{
    			cin >> map[h][0] >> map[h][1] >> map[h][2] >> map[h][3]; // volume - weight - number - value
    		}
    
    		ret = inference(map, N, V, W);
    
    		cout << "computation " << i << " = " << computation << endl;
    		cout << "CASE #" << i << " = " << ret << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

Start of the program, start = 0
    Start of the program, start = 0
    
    computation 1 = 245357
    CASE #1 = 72
    computation 2 = 245357
    CASE #2 = 72
    
    End of the program, end = 16
    End of the program, end = 16
    Total time taken by CPU: 0.016000
    Exiting of the program...
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/2020061123153778.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center