1.1 題目
Given n items with size A[i], an integer m denotes the size of a backpack. How full you can fill this backpack?
NoteYou
can not divide any item into small pieces
.Example
If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select 2, 3 and 5, so that the max size we can fill this backpack is 10.
If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.
You function should return the max size we can fill in the given backpack.
在n個(gè)物品中挑選若干物品裝入背包煤蹭，最多能裝多滿？假設(shè)背包的大小為m卧檐，每個(gè)物品的大小為A[i]驳棱。
1.2 解題思路
本題是典型的01背包問(wèn)題员萍，每種類型的物品最多只能選擇一件。
State:dp[i][S]表示前i個(gè)物品，取出一些能否組成和為S體積的背包
Function:f[i][S] = f[i-1][S - A[i]] or f[i-1][S] (A[i]表示第i個(gè)物品的大小)
轉(zhuǎn)移方程想得到f[i][S]前i個(gè)物品取出一些物品想組成S體積的背包缤至。 那么可以從兩個(gè)狀態(tài)轉(zhuǎn)換得到。
（1）f[i-1][S - A[i]] 放入第i個(gè)物品康谆，并且前i-1個(gè)物品能否取出一些組成和為S-A[i] 體積大小的背包领斥。
（2）f[i-1][S]不放入第i個(gè)物品， 并且前i-1個(gè)物品能否取出一些組成和為S 體積大小的背包沃暗。
Intialize:f[1…n][0] = true; f[0][1... m]= false
初始化f[1...n][0]表示前1...n個(gè)物品月洛，取出一些能否組成和為0 大小的背包始終為真。
其他初始化為假
Answer: 尋找使f[n][S]值為true的最大的S. （S的取值范圍1到m）
1.3 解題代碼
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @return: The maximum size
*/
public int backPack(int m, int[] A) {
boolean f[][] = new boolean[A.length + 1][m + 1];
//初始化略過(guò)
for (int i = 1; i <= A.length; i++) {
for (int j = 0; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (j >= A[i-1] && f[i-1][j - A[i-1]]) {
f[i][j] = true;
}
} // for j
} // for i
for (int i = m; i >= 0; i--) {
for (int j = A.length;j>=0;j--){
if (f[j][i]) {
return i;
}
}
}
return 0;
}
}
2.1 題目
Given n items with size A[i] and value V[i], and a backpack with size m. What's the maximum value can you put into the backpack?
Note
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.
Example
Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10.
The maximum value is 9.
兩個(gè)數(shù)組孽锥，一個(gè)表示體積嚼黔，另一個(gè)表示價(jià)值，給定一個(gè)容積為m的背包惜辑，求背包裝入物品的最大價(jià)值唬涧。
2.2 解題思路
首先定義狀態(tài) K(i,w) 為 在面對(duì)第 i 件物品，且背包容量為 w 時(shí)所能獲得的最大價(jià)值 盛撑，則相應(yīng)的狀態(tài)轉(zhuǎn)移方程為： K(i,w)=max{K(i?1,w),K(i?1,w?wi)+vi}
2.3 解題代碼
public class Solution {
/**
* @param m: An integer m denotes the size of a backpack
* @param A & V: Given n items with size A[i] and value V[i]
* @return: The maximum value
*/
public int backPackII(int m, int[] A, int V[]) {
// write your code here
int[][] dp = new int[A.length + 1][m + 1];
for(int i = 0; i <= A.length; i++){
for(int j = 0; j <= m; j++){
if(i == 0 || j == 0){
dp[i][j] = 0;
}
else if(A[i] > j){//已經(jīng)裝不下A[i]
dp[i][j] = dp[(i-1)][j];
}
else{
dp[i][j] = Math.max(dp[(i-1)][j], dp[(i-1)][j-A[i-1]] + V[i-1]);
}
}
}
return dp[A.length][m];
}
}
3.1 題目
Given n kind of items with size Ai and value Vi( each item has an infinite number available) and a backpack with size m. What's the maximum value can you put into the backpack?
Notice
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.
Example
Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 15.
這道題相比上題變?yōu)椋褐貜?fù)選擇+最大價(jià)值碎节。
3.2 解題思路
和01背包問(wèn)題很類似
狀態(tài)轉(zhuǎn)移方程
不放A[i]
f[i][j] =f[i-1][j]
放A[j]
可放多個(gè)設(shè)為k，
k = j/A[i]
f[i][j] = f[i-1][j- kiA[i]] + kiA[i] 0<=ki<=k 取最大值 0<=ki*A[i]<=m
3.3 解題代碼
public class Solution {
/**
* 多重背包問(wèn)題
* 總體積是m抵卫，每個(gè)小物品的體積是A[i]
*
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i] 0 開始的 A是
* @return: The maximum size
*/
public int backPackIII(int m, int[] A) {
// write your code here
int[][] P = new int[A.length+1][m+1];// P[i][j] 前i個(gè)物品放在j的空間中的最大價(jià)值
for(int i = 0;i< A.length; i++){
for(int j = m;j>=1;j--){
if(j>=A[i]){
int k = j/A[i];// 該物品最大可以放k個(gè)
while(k>=0){
if(j>=A[i]*k){
P[i+1][j] =Math.max(P[i+1][j], P[i][j-k*A[i]] + k*A[i]);
}
k--;
}
}
else
P[i+1][j] = Math.max(P[i][j],P[i+1][j]);
}
}
return P[A.length][m];
}
}
下一篇: 9. DP_leetcode 221 Maximal Square
上一篇: 7. DP_leetcode 5 Longest Palindromic Substring最長(zhǎng)回文子串
