动态规划（dynamic programming）基础【背包问题】

川长思鸟来 2022-12-15 02:50 226阅读 0赞

***目   录***

哔哩哔哩网站——动态规划基础 背包问题(1) 01背包

哔哩哔哩网站——【动态规划】背包问题

--------------------

> **[百度百科——背包问题][Link 1]**

# 哔哩哔哩网站——动态规划基础 背包问题(1) 01背包 #

> [视频网址——哔哩哔哩网站——动态规划基础 背包问题(1) 01背包][_1_ 01]

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70][]
> 
>

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1][]
> 
> ![20201014204822515.png][]
> 
> ![20201014205127728.png][]   滚动数组

> [背包问题——优化算法——阶梯跳跃点][Link 2]

// #include "everything.h"
    #include <bits/stdc++.h> // 错误代码
    
    using namespace std;
    
    int N, V, dp[1001][100001], c[100001], w[100001]; // c重量、w价值
    
    int main()
    {
        int i, j;
        cin >> N >> V;
        for (i = 1; i <= N; i++)
            cin >> c[i] >> w[i]; // 读入每个物品的重量与收益
        for (i = 1; i <= N; i++)
        {
            for (j = V; j >= 0; j--)
            {
                if (j < c[i])
                    break;
                dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
            }
        }
        cout << dp[V] << endl;
        system("pause");
        return 0;
    }

# 哔哩哔哩网站——【动态规划】背包问题 #

> [视频网址——哔哩哔哩网站——][Link 3][【动态规划】背包问题][Link 3]

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 2][]
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 3][]
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 4][]

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 5][]

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 6][]

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 7][]
> 
> 回溯：没有与10相同的，所以物品4一定被装入背包了。背包空间为8，物体4体积为5，背包中剩余的空间“3”用来装其它物品。考虑背包容量为3的时候，最佳物品组合。--> 考虑3号物品到底有没有被装入背包 --> 若3号物品未被装入背包，考虑前两个物品装入背包的情况即可。

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 8][]

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 9][]   ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 10][]

> Java代码实现：[https://www.cnblogs.com/jiyongjia/p/13475026.html][https_www.cnblogs.com_jiyongjia_p_13475026.html]

> [代码——原文链接][Link 4]
> 
> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 11][]

package Z;
    
    import java.util.ArrayList;
    import java.util.LinkedHashMap;
    import java.util.List;
    import java.util.Map;
    
    public class Beibao {
    
    	public static void main(String[] args) {
    		Map<Integer, Integer> map = new LinkedHashMap<>();
    		map.put(2, 3);
    		map.put(3, 4);
    		map.put(4, 5);
    		map.put(5, 6);
    		System.out.print("背包可容纳最大价值：" + getMaxValue(map, 8));
    	}
    
    	private static Integer getMaxValue(Map<Integer, Integer> gems, int capacity) {
    		int[][] maxValue = new int[gems.size() + 1][capacity + 1];
    		List<Integer> gemList = new ArrayList<>();
    		int choose, notChoose;
    		for (int i = 0; i < gems.size() + 1; i++) {
    			maxValue[i][0] = 0;
    		}
    		for (int i = 0; i < capacity + 1; i++) {
    			maxValue[0][i] = 0;
    		}
    		gemList.add(0);
    		for (Integer gemKey : gems.keySet()) {
    			gemList.add(gemKey);
    		}
    
    		for (int i = 1; i < gems.size() + 1; i++) {
    			for (int j = 1; j < capacity + 1; j++) {
    				if (gemList.get(i) > j) {
    					maxValue[i][j] = maxValue[i - 1][j];
    				} else {
    					choose = gems.get(gemList.get(i)) + maxValue[i - 1][j - gemList.get(i)];
    					notChoose = maxValue[i - 1][j];
    					maxValue[i][j] = Math.max(choose, notChoose);
    				}
    			}
    		}
    
    		for (int i = 0; i < gems.size() + 1; i++) {
    			for (int j = 0; j < capacity + 1; j++) {
    				System.out.print(maxValue[i][j] + " ");
    			}
    			System.out.println();
    		}
    		getDetails(maxValue, gems, gemList, gems.size() + 1, capacity + 1);
    		return maxValue[gems.size()][capacity];
    	}
    
    	private static void getDetails(int[][] maxValue, Map<Integer, Integer> gems, 
    			List<Integer> gemList, int rows, int cols) {
    		List<Integer> details = new ArrayList<>();
    		while (rows > 1 && cols > 1) {
    			if (maxValue[rows - 1][cols - 1] != maxValue[rows - 2][cols - 1]) {
    				details.add(rows - 1);
    				rows--;
    				cols = cols - 1 - gemList.get(rows - 1);
    			} else {
    				rows--;
    			}
    		}
    		System.out.println("装入背包的有：");
    		for (int i = 0; i < details.size(); i++) {
    			System.out.println(
    					"体积为" + gemList.get(details.get(i)) + ",价值为" + gems.get(gemList.get(details.get(i))) + "的石头");
    		}
    	}
    
    }

> 多谢观看、

[Link 1]: https://baike.baidu.com/item/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98/2416931?fr=aladdin
[_1_ 01]: https://www.bilibili.com/video/BV1ob411C7gg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70]: /images/20221123/bd921ed05b6a4525b5898491abe609b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 1]: /images/20221123/25ab1e6431f84696aba2a5b12c175d24.png
[20201014204822515.png]: /images/20221123/08dce1b5fb4f4165adf2804f5e378ab0.png
[20201014205127728.png]: /images/20221123/842d573106e2430abd37799bf98b4247.png
[Link 2]: https://blog.csdn.net/qq_37706228/article/details/83928307
[Link 3]: https://www.bilibili.com/video/BV1K4411X766
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 2]: /images/20221123/0a67d6db9cf54671b72ed87a9c551b41.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 3]: /images/20221123/048b91915f5e4e0bbcb690eccef813df.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 4]: /images/20221123/ced3ed76f3f34e4d8523940d73b1b869.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 5]: /images/20221123/28fe37dfce6d4c09863e0316d42a3af7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 6]: /images/20221123/6c6c4bd55faa4b5abe61fd82fd21b6b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 7]: /images/20221123/0c7aff9a65f94f299e008609acf9f3ea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 8]: /images/20221123/41ffb4a9860c4b1db01c5d37c65f2d6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/2020101421480476.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 10]: /images/20221123/8ef2ff98a46d463a8ba03a3ab54d05e2.png
[https_www.cnblogs.com_jiyongjia_p_13475026.html]: https://www.cnblogs.com/jiyongjia/p/13475026.html
[Link 4]: https://blog.csdn.net/TreeCode/article/details/108903221
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTEzNQ_size_16_color_FFFFFF_t_70 11]: /images/20221123/08059f5dfb21424490244922593bd832.png