題目要求

P1049題目鏈接

分析

這種題不能貪心，大家都懂的，應(yīng)該使用DP。
比如容量為7，有三個物品體積是1,2,5，你要是先裝小的，就只能裝3，剩下4，但實際上可以裝的只剩一個。
如果容量為10，三個物品體積是2,2,2,2,2,9，你要是先裝最大的，就只能裝9，剩下1，但實際上可以裝滿的。

嗯，本題可以看做一個基本的0/1背包問題：
一個物體的體積，關(guān)系著它的價值，也關(guān)系著它的代價。

題目變?yōu)?#xff1a;
有一個箱子容量為V（正整數(shù)，0 < V ≤ 20000），同時有n個物品（0 < n ≤ 30），每個物品有一個代價（體積）和一個價值（體積）。要求這n個物品中，任取若干個裝入箱內(nèi)，在不超出箱子容量的情況下，使總價值最大。

所以狀態(tài)轉(zhuǎn)移方程是：$f[j]=Math.max(f[j],f[j?cost[i]]+cost[i])$

AC代碼（Java語言描述）

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int v = scanner.nextInt(), num = scanner.nextInt();int[] cost = new int[num];int[] f = new int[v+1];for (int i = 0; i < num; i++) {cost[i] = scanner.nextInt();}scanner.close();for (int i = 0; i < num; i++) {for (int j = v; j >= cost[i]; j--) {f[j] = Math.max(f[j], f[j-cost[i]]+cost[i]);}}System.out.println(v-f[v]);} }

總結(jié)

以上是生活随笔為你收集整理的动态规划求解装箱问题（洛谷P1049题题解，Java语言描述）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。