0-1背包问题
给n个重量为w1,w2,w3,...,wn，且价值为v1,v2,v3,...vn的物品和容量为C的背包，每个东西只能选择用一次或者不用(这就是0-1的由来)，求这个物品的一个最有价值的子集，使得在满足背包容量的前提下，包内价值最大。
动态规划解决
我们定义dp[i][j]为在有i个物品且背包容量为j的前提下，包内最大的价值；
那么则有
1 不放第i个物品时，dp[i][j]=dp[i-1][j]
2 放第i个物品时，dp[i][j]=dp[i-1][j-w[i]]+v[i]
所以状态转移方程就是dp[i][j]=max(dp[i-1][j],dp[i][j]=dp[i-1][j-w[i]]+v[i])
public class KnapSack01 {
public static int knapSack(int[] w, int[] v, int C) {
int size = w.length;
if (size == 0) {
return 0;
}
int[][] dp = new int[size][C + 1];
//不放物品时显然价值为0
for (int i = 0; i <= C; i++) {
dp[0][i] = 0;
}
//背包容量为0时价值也为0
for(int i=0;i<=size;i++)
dp[i][0]=0;
//填充其他行和列
for (int i = 1; i < size; i++) {
for (int j = 0; j <= C; j++) {
dp[i][j] = dp[i - 1][j];
if (w[i] <= j) {
dp[i][j] = Math.max(dp[i][j], v[i] + dp[i - 1][j - w[i]]);
}
}
}
return dp[size - 1][C];
}
public static void main(String[] args) {
int[] w = {2, 1, 3, 2};
int[] v = {12, 10, 20, 15};
System.out.println(knapSack(w, v, 5));
}
}
根据上述代码，时间复杂度为O(sizeC),这已经是最快的了，无法再简化，但是空间复杂度O(sizeC)可以在简化，这里我们使用了二维数组，因此接下来使用一维数组存储
这里我们定义dp[i]为容量为i时的最大价值，则有推导
dp[i]=dp[i-1] 不放下一个物品
dp[i]=dp[i-w[j]]+v[j] 放下一个物品
所以状态转移方程就是dp[i]=max(dp[i-1],dp[i-w[j]]+v[j]).
public class KnapSack01 {
public static int knapSack(int[] w, int[] v, int C) {
int size = w.length;
if (size == 0) {
return 0;
}
int[] dp = new int[C + 1];
//初始化所有价值都为0，其实只要保证是一个很小的数就行
for (int i = 0; i <= C; i++) {
dp[i] =0;
}
for (int i = 1; i < size; i++) {
for (int j = C; j >= w[i]; j--) {
dp[j] = Math.max(dp[j], v[i] + dp[j - w[i]]);
}
}
return dp[C];
}
public static void main(String[] args) {
int[] w = {2, 1, 3, 2};
int[] v = {12, 10, 20, 15};
System.out.println(knapSack(w, v, 5));
}
}
这样空间复杂度就是O(C)了。
说这么多，来看真题
![E(0EZK9QZ@RNL3(XCBGPL7.png
这道题可以理解为每张邮票的价值都是1，现在要求一个最佳子集使得邮票的价值最小也就是邮票的数量最小，显然是0-1背包问题，下面是代码
#include <stdio.h>
int main()
{
int weight[21];
int f[101];
int m,n,i,j;
while(scanf("%d",&m)!=EOF)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&weight[i]);
f[0]=0;
//初始化
for(i=1;i<=m;i++)
f[i]=1000000;
for(i=1;i<=n;i++)
{
for(j=m;j>=weight[i];j--)
{
f[j]=f[j]<f[j-weight[i]]+1?f[j]:f[j-weight[i]]+1;
}
}
if(f[m]>0&&f[m]<=n)
printf("%d",f[m]);
else
printf("0");
}
return 0;
}
恩，今天就到这里，下次有时间看一下其他背包问题，这个0-1背包也要继续练习。
但行好事，莫问前程！
网友评论