本文主要是介绍63、背包问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
背包问题
题目描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式:
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。
输出格式:
输出一个整数,表示最大价值。
数据范围:
- 0 < N , V ≤ 1000 0 < N,V ≤ 1000 0<N,V≤1000
- 0 < v i , w i ≤ 1000 0<vi,wi≤1000 0<vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
8
Solution
思路:
-
状态:
dp[i][j]
表示只看前i
个物品,总体积不超过j
的情况下,背包中物品的最大价值最后答案就是
dp[N][V]
-
状态转移:找最后一个不同点,也就是选最后一个物品的不同方案。对于
dp[i][j]
有两种情况:-
不选择当前的第件物品/第i件物品比背包容量要大
则
dp[i][j] = dp[i-1][j]
-
选择当前的第i件物品(潜在要求第i件物品体积小于等于背包总容量,即
v[i] >= j
)则
dp[i][j] = dp[i-1][j-v[i]] + w[i]
上面两种情况取max作为当前的最优解。
-
-
边界:
dp[0][0] = 0
-
注意一些细节:
- 如果
j
表示体积正好是j
的话,那么答案就需要遍历求max
。如果表示的是 不超过j
的话,答案就是dp[N][V]
。 - 如果题目要求背包必须放满,那么
dp[0] [0…V]
中仅仅有dp[0][0]
为0,其余值需被设置为-INF
,返回dp[V]。 - 如果并没有要求必须把背包装满,而是只希望总价值尽量大,初始化时应该将
dp[0...V ]
全部设为0, 返回dp[V]。 i
和j
从1开始循环。
- 如果
普通版:
import java.util.*;class Main{public static void main(String[] args){// 输入数据Scanner scan = new Scanner(System.in);int N = scan.nextInt();int V = scan.nextInt();int[] v = new int[N + 10];int[] w = new int[N + 10];for(int i = 1; i <= N; i++){v[i] = scan.nextInt();w[i] = scan.nextInt();}scan.close();// 开始dpint[][] dp = new int[N + 10][V + 10];for(int i = 1; i <= N; i++){for(int j = 1; j <= V; j++){// 放进去和不放进去取最大值dp[i][j] = dp[i - 1][j];if(j >= v[i])dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}// int res = 0;// for(int i = 0; i <= V; i++) res = Math.max(res, dp[N][i]);// System.out.println(res);// 或者System.out.println(dp[N][V]);}
}
进阶版:
dp[j]
表示体积不超过j
的情况下的最大价值。dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
,看j
,第二维要不就是用j
,要不是就是用比j
小的数。- 如果j从小往大循环,后面的dp[j]可能已经被前面的更新了,相当于dp[i][j - v[i]]
- 所以让
j
从大到小循环。把第一维去掉,变成了dp[j] = max(dp[j], dp[j-v[i] + w[i])
,比如计算第二层的时候,dp[j-v[i]]
还没有在第二层被更新过(因为j-v[i]
比j
小),所以这个时候的dp[j-v[i]]
存的是上一层的状态,也就是dp[i-1][j-v[i]]
import java.util.*;class Main{public static void main(String[] args){// 输入数据Scanner scan = new Scanner(System.in);int N = scan.nextInt();int V = scan.nextInt();int[] v = new int[N + 10];int[] w = new int[N + 10];for(int i = 1; i <= N; i++){v[i] = scan.nextInt();w[i] = scan.nextInt();}scan.close();// 开始dpint[] dp = new int[V + 10];for(int i = 1; i <= N; i++){for(int j = V; j >= v[i]; j--){// 放进去和不放进去取最大值dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);}}// 如果初始化:dp[0]为0,其他为负无穷,就要遍历取最大值。// 这种情况对应体积恰好为V的价值,保证所有的状态从0转移来//// 如果初始化:dp[i]都为0,dp[V]也是最大值。假设dp[k]为最大值。// dp[k]从0转移过来,那dp[V]从dp[V-k]转移过来,是一样的System.out.println(dp[V]);}
}
这篇关于63、背包问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!