小明的背包1（蓝桥杯）

题目描述

小明有一个容量为 V 的背包。

这天他去商场购物，商场一共有 N 件物品，第 i 件物品的体积为 wi​，价值为 vi​。

小明想知道在购买的物品总体积不超过 V 的情况下所能获得的最大价值为多少，请你帮他算算。

输入描述

输入第 1 行包含两个正整数N,V，表示商场物品的数量和小明的背包容量。

第 2∼N+1 行包含 2 个正整数w,v，表示物品的体积和价值。

1≤N≤10^2，1≤V≤10^3，1≤wi​,vi​≤10^3。

输出描述

输出一行整数表示小明所能获得的最大价值。

输入输出样例

示例 1

输入

5 20
1 6
2 5
3 8
5 15
3 3 

输出

37

这题为动态规划问题，我们定义一个数组dp[][]，数组dp[i][j]表示将前i个物品装入重量为j的背包中，其存储的值就是当前的价值。用数组w[i]来存储当前物体的体积，v[i]来存储当前物体的价格。

一：当第i个物体体积w[i]比当前的背包体积j大时，放不进背包，因为放不进背包，所以这时价值和装前i-1物体背包一样，dp[i][j]=dp[i-1][j]。

二：当第i个物体体积w[i]比背包体积j小时，我们有放和不放两种选择。

1：如果放，在放之前其i-1背包价值为dp[i-1][j]，那么在放之后其背包j体积会变小为j-w[i]，价值会变成dp[i-1][j-w[i]]+v[i]。

2：如果不放，则dp[i][j]=dp[i-1][j]

所以状态方程为min(dp[i-1][j-w[i]]+v[i],dp[i-1][j])

import java.util.*;
public class Main{
	static int n=3031;
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int N=in.nextInt();
		int V=in.nextInt();
		int []w=new int[N+1];//物品的体积
		int []v=new int[N+1];//物品的价值
		for(int i=1;i<=N;i++) {
			w[i]=in.nextInt();
			v[i]=in.nextInt();
			
		}
	int [][]dp=new int[n][n];
	for(int i=0;i<=N;i++)
		Arrays.fill(dp[i], 0);//初始化dp数组为0
	for(int i=1;i<=N;i++) {
		for(int j=0;j<=V;j++) {
			if(w[i]>j)
				dp[i][j]=dp[i-1][j];
			else
				dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
		}
	}
	
	System.out.println(dp[N][V]);
	
	   
}
}