完全背包問題
題目來源：背包九講
時間限制：1000ms 記憶體限制：64mb
題目描述
有 \(N\) 件物品和一個容量是 \(V\) 的背包，每種物品都有 無限 件可用，
第 \(i\) 件物品的體積是 \(v_i\)，價值是 \(w_i\)，
求解將哪些物品裝入背包，可使這些物品的總體積不超過背包容量，且總價值最大，
輸出最大價值，
輸入格式
第一行兩個整數，\(N\)，\(V\)，用空格隔開，分別表示物品數量和背包容積，
接下來有 \(N\) 行，每行兩個整數 \(v_i\),\(w_i\)，用空格隔開，分別表示第 \(i\) 件物品的體積和價值，
輸出格式
輸出一個整數，表示最大價值，
資料范圍
0 < \(N\),\(V\) ≤ 1000
0 < \(v_i\),\(w_i\) ≤ 1000
樣例輸入
4 5
1 2
2 4
3 4
4 5
樣例輸出
10
解題思路：動態規劃
只需要將之前的《01背包問題》的第三個解法中的第二層回圈反著來就可以了，
解題代碼-Java
import java.util.*;
public class Main {
public static int N = 1010;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int v = input.nextInt();
int[] dp = new int[N];
for (int i = 1; i <= n; i++) {
int vi = input.nextInt();
int wi = input.nextInt();
for (int j = vi; j <= v; j++) {
dp[j] = Math.max(dp[j], dp[j - vi] + wi);
}
}
System.out.println(dp[v]);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251490.html
標籤：其他