【算法系列】——代码实践动态规划

ゝ一纸荒年。 2022-06-08 11:40 127阅读 0赞

之前小编对算法的理解都停留在思想的层面，从未尝试过的代码实践，大家都是想出来和做出来的差距还是比较大的。小编在网上找了一个情景，所以一个实际情况的具体解析吧。

# 问题情境 #

根据题目说明很明显发现这是一个0-1背包问题，之前在思考动态规划问题的时候，遵循是先将各种符合动态规划的所有数据都存放到二维表格中，然后根据最大价值再去推算这个背包中需要包含哪几件物品。

![Center][]

![Center 1][]

# 代码 #

package test;
    
    import java.util.ArrayList;
    import java.util.List;
    
    
    public class dynamicProgramming {
    
    	//定义全局变量数据组
    	public static void main(String[] args) {
    		List<Item> itemList = new ArrayList<Item>();
    		Item item = new Item();
    		item.setId(1);
    		item.setSize(200);
    		item.setV(50);
    		itemList.add(item);
    		Item item1 = new Item();
    		item1.setId(2);
    		item1.setSize(180);
    		item1.setV(30);
    		itemList.add(item1);
    		Item item2 = new Item();
    		item2.setId(3);
    		item2.setSize(225);
    		item2.setV(45);
    		itemList.add(item2);
    		Item item3 = new Item();
    		item3.setId(4);
    		item3.setSize(200);
    		item3.setV(25);
    		itemList.add(item3);
    		Item item4 = new Item();
    		item4.setId(5);
    		item4.setSize(50);
    		item4.setV(5);
    		itemList.add(item4);
    		int w = 100;
    		/*上述内容模拟的数据*/
    		int[] i =dynamic(itemList, w+1);
    		for (int j = 0; j < i.length; j++) {
    			System.out.print(i[j]+";");
    		}
    
    	}
    	/**
    	 * 
    	 * @param itemList 物品的集合
    	 * @param w 背包的总重量
    	 * @return
    	 */
    	public static int[] dynamic(List<Item> itemList,int w){
    		int n = itemList.size();//获取食物的项数
    		int[][] c = new int[n][w];//定义表格
    		int[] r = new int[n];
    		//初始化容量为空的数据
    		for (int i = 0; i < n; i++) {
    			c[i][0]=0;
    		}
    		//初始化没有物品的数据
    		for (int i = 0; i < w; i++) {
    			c[0][i]=0;
    		}
    		for (int i = 1; i < n; i++) {
    			for (int j = 0; j < w; j+=5) {
    				if (j<itemList.get(i).getV()) {
    					c[i][j]=c[i-1][j];
    //					没在背包中，则赋值为0
    					r[i]=0;
    				}else if (c[i-1][j-itemList.get(i).getV()]+itemList.get(i).getSize()<c[i-1][j]){
    					c[i][j]=c[i-1][j];
    //					没在背包中，则赋值为0
    					r[i]=0;
    				}else {
    					c[i][j]=c[i-1][j-itemList.get(i).getV()]+itemList.get(i).getSize();
    //					在背包中，则赋值为1
    					r[i]=1;
    				}
    			}
    		}
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < w; j+=5) {
    				System.out.print(c[i][j]+";");
    			}
    			System.out.println();
    		}
    		return r;
    	}
    	
    	
    	
    
    }

在代码 实际过程发现，其实在计算二维表的过程，每个价值的构成包含那几件物品其实均已知，没有必要再用循环去判断。

运行结果

![Center 2][]

# 【总结】 #

在思路正确的情况下，还的在实践的过程，才能发现代码到底有哪地方可以继续优化！功力尚浅，慢慢学习吧！

[Center]: /images/20220608/8d1b2237b04244fd803c72b9174984ca.png
[Center 1]: /images/20220608/51a27684078a49ceaa3c7c1ff4eef27d.png
[Center 2]: /images/20220608/f0ebbdd92f7440c88b0cac659a4c18dc.png