动态规划--0-1背包问题1

package com.duoduo.day316;
/**
 * 0-1背包问题
 * 
 * 问题描述：有n个物品，每个物品的重量为w[i], 价值为v[i]，购物车容量为W，选择若干个物品放入购物车
 * 限制：在不超过容量的前提下使获得的价值最大
 * 思路：和之前的贪心算法（背包问题）不同，故分析最优子结构后，采用动态规划思想求解
 * 
 * c[i][j]: 前i件物品放入一个容量为j的购物车可以获得的最大价值
 *        购物车容量不足，肯定不能放入：
 *       c[i][j]=  c[i-1][j]    j<wi
 *        购物车容量足，看放入，不放入哪种情况获得的价值最大：
 *       c[i][j]=  max{c[i-1][j],c[i-1][j-w[i]]+v[i]    j>=wi
 *       
 * @author 多多
 *
 */
import  java.util.Scanner;
public class Test4_9 {
	public static void main(String [] args) {
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入物品的个数n:");
		int n=sc.nextInt();      //物品的个数
		System.out.println("请输入购物车的容量:");
		int W=sc.nextInt();
		System.out.println("请依次输入每个物品的重量 w 和价值 v,用空格分开:");
		int [] w=new int[n+1];     //每个物品的重量
		int [] v=new int[n+1];     //每个物品的价值
		for(int i=1;i<=n;i++) {    //存入键入的数据
			w[i]=sc.nextInt();
			v[i]=sc.nextInt();
		}
		
		int [][] c=new int[n+1][W+1];  //c[i][j] : 前i件物品放入一个容量为j的购物车可以获得的最大价值
		//初始化数组 c[i][j]
		for(int i=0;i<=n;i++)          
			c[i][0]=0;
		for(int j=0;j<=W;j++)
			c[0][j]=0;
		
		/*计算c[i][j]的递归式
		购物车容量不足，肯定不能放入：
		        c[i][j]=  c[i-1][j]                j<wi
	        购物车容量足，看放入，不放入哪种情况获得的价值最大：
		        c[i][j]=  max{c[i-1][j],c[i-1][j-w[i]]+v[i]   j>=wi
		*/
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=W;j++) {
				if(j<w[i]) {
					c[i][j]=c[i-1][j];  //购物车容量不足，肯定不能放入：
				}else {
					c[i][j]=max(c[i-1][j],c[i-1][j-w[i]]+v[i]);//购物车容量足，看放入，不放入哪种情况获得的价值最大：
				}	
			}
		}
		System.out.println("装入购物车的最大价值："+c[n][W]);
		
		/*逆向构造最优解
		 * 根据c[i][j]数组的计算结果  逆向  逆推 用一个一维数组x[]记录解向量  
		 * x[i]=1  表示第i个物品放入购物车
		 * x[i]=0  表示不放入购物车 
		 * */
		int [] x=new int[n+1];
		int j=W;
		for(int i=n;i>0;i--) {
			if(c[i][j]>c[i-1][j]) {  //说明第i个物品放入购物车 标记为1 且 购物车容量--物品重量
				x[i]=1;
				j-=w[i];
			}else {
				x[i]=0;             //否则 未放入 则标记为0
			}
		}
		
		System.out.println("装入购物车的物品为:");
		for(int i=1;i<=n;i++) {
			if(x[i]==1)
				System.out.print(i+" ");   //打印标记为1 的物品
		}
	}
	
		

	private static int max(int i, int j) {
		return i>j? i:j ;
	}

}

结果：

时间复杂度：主要是两层嵌套 O(n*W)

空间复杂度：c[n][W]  O(n*W)