完全背包问题 857 java题解

问题描述

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

输入格式

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

输出格式

　　一個數，為最大價值。

样例输入

3 20
15 16
6 6
7 5

样例输出

18

数据规模和约定

　　N, M<=1000。

输入时是无序给的一些物品重量和物品价值，需要先排序存放至数组中，转换成常规问题求解。同样列出动态转移方程：dp[j] = max ( dp[j - w[i]] + v[i] , dp[j] )。

思路和切割木头一样。传送门：切原木问题

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] split = br.readLine().split(" ");
		int n = Integer.parseInt(split[0]);
		int total = Integer.parseInt(split[1]);
		List list = new ArrayList<>();
		for(int i = 0; i < n;i++) {
			split = br.readLine().split(" ");
			int key = Integer.parseInt(split[0]);
			int value = Integer.parseInt(split[1]);
			list.add(new Temp857(key, value));
		}
		Collections.sort(list);
		int []w = new int[n];
		int []v = new int[n];
		for(int i = 0; i < list.size();i++) {
			w[i] = list.get(i).key;
			v[i] = list.get(i).value;
		}
		int []dp = new int [total + 1];
		for(int i = 0; i < n;i++) {
			for(int j = w[i];j <= total;j++) {
				dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
			}
		}
		System.out.println(dp[total]);
	}
}
class Temp857 implements Comparable{
	int key;
	int value;
	
	public Temp857(int key, int value) {
		this.key = key;
		this.value = value;
	}

	@Override
	public int compareTo(Temp857 o) {
		return this.key - o.key;
	}
	
}