算法训练 完全背包问题 java 蓝桥杯

问题描述

　　有一個背包，容量為M。有N種物品，每種物品有其體積Wi與價值Vi。將這些物品的一部分放入背包，每種物品可以放任意多個，要求總體積不超過容量，且總價值最大。

输入格式

　　第一行為N, M。
　　之後N行，每行為Wi, Vi。

输出格式

　　一個數，為最大價值。

样例输入

3 20
15 16
6 6
7 5

样例输出

18

数据规模和约定

　　N, M<=1000。

import java.util.Scanner;

public class Main {
static int M;
static int N;
static int dp[][];
static int Wi[];
static int Vi[];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		 N=sc.nextInt();//物品种类
		 M=sc.nextInt();//物品容量
		 Wi=new int[N+1];//物品容量
		 Vi=new int[N+1];//物品价值
		for (int i = 1; i <=N; i++) {
			Wi[i]=sc.nextInt();
			Vi[i]=sc.nextInt();
		}
		dp=new int[N+1][M+1];
		Complete(dp);
	}
	public static void Complete(int dp[][]) {
		for (int i = 0; i <=M; i++) {
			dp[0][i]=0;
		}
		for (int i = 1; i <=N; i++) {
		for (int j = 0; j <=M; j++) {
		for (int k = 0; k <=M/Wi[i]; k++) {
			if (j>=k*Wi[i]) {
				dp[i][j]=Math.max(dp[i-1][j-k*Wi[i]]+k*Vi[i], dp[i][j]);
			}else {
				dp[i][j]=dp[i][j];
			}
		}	
		}	
		}
		System.out.println(dp[N][M]);
	}
}

思路：前面的都是0，这个采用动态规划。