基础背包问题 - 无界背包问题或完全背包问题 - 深度优先搜索 (递归)

「爱情、让人受尽委屈。」 2023-02-16 12:13 37阅读 0赞

#  基础背包问题 - 无界背包问题或完全背包问题 - 深度优先搜索 (递归) #

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

有 `N` 种物品和一个承受最大重量为 `W` 的背包。第 `i` 种物品的重量是 `w[i]`，价值是 `v[i]`。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

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

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

## 2. 无界背包问题或完全背包问题 ##

有 `N` 种物品和一个容量是 `V` 的背包，每种物品都有无限件可用。第 `i` 种物品的体积是  v i v\_i vi，价值是  w i w\_i wi。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大，输出最大价值 10。

**输入格式**

2   // 测试用例个数
    4 5 // N = 4 物品的类别数，V = 5 背包的容量，最大价值 10
    1 2 // v[0] = 1，w[0] = 2
    2 4 // v[1] = 2，w[1] = 4
    3 4 // v[2] = 3，w[2] = 4
    4 5 // v[3] = 4，w[3] = 5
    4 5 // N = 4 物品的类别数，V = 5 背包的容量，最大价值 10
    1 2
    2 4
    3 4
    4 5
    2 10 // N = 2 物品的类别数，V = 10 背包的容量，最大价值 10
    5 5
    7 8
    4 10 // N = 4 物品的类别数，V = 10 背包的容量，最大价值 12
    7 9
    4 5
    3 3
    2 1

两个整数 `N` `V`，用空格隔开，分别表示物品种数和背包容量。接下来有 `N` 行，每行两个整数  v i v\_i vi  w i w\_i wi，用空格隔开，分别表示第 `i` 种物品的体积和价值。 v i v\_i vi 表示体积， w i w\_i wi 表示价值。

0 < N , V ≤ 1000 0 < N, V ≤ 1000 0<N,V≤1000  
 0 < v i , w i ≤ 1000 0 < v\_\{i\}, w\_\{i\} ≤ 1000 0<vi,wi≤1000

4
    4 5
    1 2
    2 4
    3 4
    4 5
    4 5
    1 2
    2 4
    3 4
    4 5
    2 10
    5 5
    7 8
    4 10
    7 9
    4 5
    3 3
    2 1

## 2.1 dfs\_v1 ##

/*
    ============================================================================
    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][2], int N, int V, int sumvolume, int sumvalue, int *max_value, int step)
    {
    	if (sumvolume > V)
    	{
    		return;
    	}
    
    	if ((sumvalue > *max_value))
    	{
    		*max_value = sumvalue;
    	}
    
    	if (step >= N)
    	{
    		computation++;
    		return;
    	}
    
    	int addvolume = 0, addvalue = 0;
    
    	// 选这类物品，然后选下一类
    	dfs_v1(map, N, V, sumvolume + map[step][0], sumvalue + map[step][1], max_value, step + 1);
    
    	// 选这类物品，然后继续选择同类
    	dfs_v1(map, N, V, sumvolume + map[step][0], sumvalue + map[step][1], max_value, step);
    
    	// 不选这类物品，然后选下一类
    	dfs_v1(map, N, V, sumvolume, sumvalue, max_value, step + 1);
    
    	return;
    }
    
    int inference(int map[100][2], int N, int V)
    {
    	int ret = 0;
    	int max_value = INT_MIN;
    	int step = 0;
    	int sumvolume = 0;
    	int sumvalue = 0;
    
    	dfs_v1(map, N, V, sumvolume, sumvalue, &max_value, step);
    
    	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;
    		int map[100][2] = { 0 };
    
    		computation = 0;
    
    		cin >> N >> V;
    
    		for (int h = 0; h < N; h++)
    		{
    			cin >> map[h][0] >> map[h][1]; // volume - value
    		}
    
    		ret = inference(map, N, V);
    
    		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 = 51
    CASE #1 = 10
    computation 2 = 51
    CASE #2 = 10
    computation 3 = 7
    CASE #3 = 10
    computation 4 = 83
    CASE #4 = 12
    
    End of the program, end = 6
    End of the program, end = 6
    Total time taken by CPU: 0.006000
    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/20200609233150114.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center