题目
有 种物品和一个容量是 的背包,每种物品都有无限件可用。
第 种物品的体积是 ,价值是 。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,,用空格隔开,分别表示物品种数和背包容积。
接下来有 行,每行两个整数 ,用空格隔开,分别表示第 种物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例:
10
解题
方法一:动态规划
思路
思维过程:
动态规划:
- 状态定义: 表示所有只考虑前 个物品,且总体积不大于 的所有选法中能得到的最大价值。
- 状态转移方程:()。
- 初始状态:只考虑前 个物品的时候没有物品可选,最大价值一定是 。
代码
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int c = (int) in.nval;
int[] v = new int[n + 1], w = new int[n + 1];
for (int i = 1; i <= n; ++i) {
in.nextToken();
v[i] = (int) in.nval;
in.nextToken();
w[i] = (int) in.nval;
}
int[][] dp = new int[n + 1][c + 1];
for (int i = 1; i <= n; ++i) {
int vi = v[i], wi = w[i];
for (int j = 0; j <= c; ++j) {
for (int k = 0; k * vi <= j; ++k) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * vi] + k * wi);
}
}
}
System.out.println(dp[n][c]);
}
}
#include <iostream>
using namespace std;
const int N = 1010;
int n, c;
int v[N], w[N], dp[N][N];
int main() {
scanf("%d%d", &n, &c);
for (int i = 1; i <= n; ++i) scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; ++i) {
int vi = v[i], wi = w[i];
for (int j = 0; j <= c; ++j) {
for (int k = 0; k * vi <= j; ++k) {
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * vi] + k * wi);
}
}
}
printf("%d\n", dp[n][c]);
return 0;
}
优化
原式:f[i][j] = max(f[i-1][j-k*vi] + k*wi)
展开:f[i][j] = max(f[i-1][j], f[i-1][j-vi]+wi, f[i-1, j-2*vi]+2*wi, f[i-1, j-3*vi]+3*wi, ...)
f[i][j-vi] = max( f[i-1][j-vi], f[i-1, j-2*vi]+wi, f[i-1, j-3*vi]+2*wi)
代换:f[i][j] = max(f[i-1][j], f[i][j-vi] + wi)
把 通过等式代换构造得与 无关,这样就可以省掉一层循环
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int c = (int) in.nval;
int[] v = new int[n + 1], w = new int[n + 1];
for (int i = 1; i <= n; ++i) {
in.nextToken();
v[i] = (int) in.nval;
in.nextToken();
w[i] = (int) in.nval;
}
int[][] dp = new int[n + 1][c + 1];
for (int i = 1; i <= n; ++i) {
int vi = v[i], wi = w[i];
for (int j = 0; j <= c; ++j) {
dp[i][j] = dp[i - 1][j];
if (vi <= j) dp[i][j] = Math.max(dp[i][j], dp[i][j - vi] + wi);
}
}
System.out.println(dp[n][c]);
}
}
滚动数组优化
每次状态转移只用到了上一行的数据,可以进行滚动数组优化。
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int c = (int) in.nval;
int[] v = new int[n + 1], w = new int[n + 1];
for (int i = 1; i <= n; ++i) {
in.nextToken();
v[i] = (int) in.nval;
in.nextToken();
w[i] = (int) in.nval;
}
int[][] dp = new int[2][c + 1];
int curr = 0;
for (int i = 1; i <= n; ++i) {
int vi = v[i], wi = w[i];
for (int j = 0; j <= c; ++j) {
dp[curr][j] = dp[curr ^ 1][j];
if (vi <= j) dp[curr][j] = Math.max(dp[curr][j], dp[curr][j - vi] + wi);
}
curr ^= 1;
}
System.out.println(dp[curr ^ 1][c]);
}
}
滚动数组再优化
每次状态转移时都只会用到这一次比 小的列,所以可以从前向后迭代用新的状态来覆盖旧状态。
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
in.nextToken();
int c = (int) in.nval;
int[] v = new int[n + 1], w = new int[n + 1];
for (int i = 1; i <= n; ++i) {
in.nextToken();
v[i] = (int) in.nval;
in.nextToken();
w[i] = (int) in.nval;
}
int[] dp = new int[c + 1];
for (int i = 1; i <= n; ++i) {
int vi = v[i], wi = w[i];
for (int j = vi; j <= c; ++j) {
dp[j] = Math.max(dp[j], dp[j - vi] + wi);
}
}
System.out.println(dp[c]);
}
}
#include <iostream>
using namespace std;
const int N = 1010;
int n, c;
int v[N], w[N], dp[N];
int main() {
scanf("%d%d", &n, &c);
for (int i = 1; i <= n; ++i) scanf("%d%d", &v[i], &w[i]);
for (int i = 1; i <= n; ++i) {
const int& vi = v[i], & wi = w[i];
for (int j = vi; j <= c; ++j) {
dp[j] = max(dp[j], dp[j - vi] + wi);
}
}
printf("%d\n", dp[c]);
return 0;
}
我们发现 0-1背包问题 与 完全背包问题 的最终优化代码只有状态转移时的迭代顺序不同:
评论区