第一章动态规划（七）
程序员文章站
2022-07-13 11:30:31
...
例题：货币系统
原题链接
【题目描述】
给你一个n种面值的货币系统，求组成面值为m的货币有多少种方案。
【输入】
第一行为n和m。
【输出】
一行，方案数。
【输入样例】
3 10 //3种面值组成面值为10的方案
1 //面值1
2 //面值2
5 //面值5
【输出样例】
10 //有10种方案
————————————————————————————————————————————————
完全背包求方案数
n 种面值----n 件物品
面值为 m —容量为 m 的背包
import java.util.Scanner;
public class Main {
static int N = 3010;
static int n;
static int m;
static long[] f = new long[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
f[0] = 1;
for(int i = 0;i < n;i++) {
int a = sc.nextInt();
for(int j = a;j <= m;j++) {
f[j] += f[j - a];
}
}
sc.close();
System.out.println(f[m]);
}
}
例题：532. 货币系统
————————————————————————————————————————————————————
若两个货币系统（n, a） 和 （m, b）等价，有如下性质
性质1：a1,a2,…,an一定都可以用若干个 bi 表示出来
性质2：在最优解中,b1,b2,…bm一定都是从a1,a2,…,an中选择的
（反证法，假设在最优解中存在某个 bi 不属于任意一个 ai，而 bi 可以用若干个 ai 表示出来，因为两个系统等价嘛，比如 bi = a1 + a2 + a3，因为每个 ai 各不相同，所以 bi > a1, a2, a3，同时由性质1可知，bi 可以用其他 bj 表示出来，那这个 bi 就没必要存在了，与假设矛盾）
性质3：b1,b2,…,bm一定不能被其他bi表示出来
（如果某个数 bi 能被其他的 bj 表示出来，那 bi 就没必要存在了）
步骤
由于数据中不存在负数，所以一定是大面值由小面值表示出来，将a[]数组从小到大排序
(1)若ai能被a0~a(i-1)表示出来，它就没必要存在，则一定不选它
(2)若ai不能被a0~a(i-1)表示出来，则一定选
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
static int N = 110;
static int M = 25010;
static int[] a = new int[N];
static int[] f = new int[M];
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(reader.readLine().trim());
while(T-- > 0) {
int n = Integer.parseInt(reader.readLine().trim());
String[] s1 = reader.readLine().split(" ");
for(int i = 0;i < n;i++) a[i] = Integer.parseInt(s1[i]);
Arrays.sort(a, 0, n);
Arrays.fill(f, 0);
f[0] = 1;
int res = 0,m = a[n - 1];
for(int i = 0;i < n;i++) {
if(f[a[i]] == 0) res ++;//凑不出来一定要
for(int j = a[i];j <= m;j++) {
f[j] = f[j] + f[j - a[i]];
}
}
System.out.println(res);
}
}
}
例题：7. 混合背包问题
摘自题解区–“小呆呆”
注意:用什么类型的转移方程只由第 i 个物品是什么类型决定
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int N = 1010;
static int[] f = new int[N];
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = reader.readLine().split(" ");
int n = Integer.parseInt(s1[0]);
int m = Integer.parseInt(s1[1]);
for(int i = 1;i <= n;i++) {
String[] s2 = reader.readLine().split(" ");
int v = Integer.parseInt(s2[0]);
int w = Integer.parseInt(s2[1]);
int s = Integer.parseInt(s2[2]);
if(s == 0) {
for(int j = v;j <= m;j++) {
f[j] = Math.max(f[j], f[j - v] + w);
}
}else {
if(s == -1) s = 1;
for(int k = 1;k <= s;k *= 2) {
for(int j = m;j >= k * v;j--) {
f[j] = Math.max(f[j], f[j - k * v] + k * w);
}
s -= k * v;
}
if(s > 0) {
for(int j = m;j >= s * v;j--)
f[j] = Math.max(f[j], f[j - s * v] + s * w);
}
}
}
System.out.println(f[m]);
}
}
例题：10. 有依赖的背包问题
————————————————————————————————————————————————
摘自–“小呆呆"和"tdly”
我们可以把有依赖的背包问题看成是分组背包问题，每一个结点是看成是分组背包问题中的一个组，子节点的每一种选择我们都看作是组内的一种物品，因此我们可以通过分组背包的思想去写。
但它的难点在于如何去遍历子节点的每一种选择，即组内的物品，我们的做法是从叶子结点开始往根节点做，并使用数组表示的邻接表来存贮每个结点的父子关系。
import java.util.Arrays;
import java.util.Scanner;
public class Main{
static int N = 110;
static int n;
static int m;
static int[] h = new int[N];
static int[] e = new int[N];
static int[] ne = new int[N];
static int idx = 0;
/*
* h数组是邻接表的头它的下表是当前节点的标号，值是当前结点第一条边的编号（其实是最后加入的那一条边），
* e数组是边的集合，它的下标是当前边的编号，数值是当前边的终点；
ne是nextedge，如果ne是-1表示当前结点没有下一条边，ne的下标是当前边的编号，数值是当前结点的下一条边的编号，
idx用于保存每一条边的上一条边的编号。
这样我们就知道了当前结点的第一条边是几，这个边的终点是那个结点，该节点的下一条边编号是几，那么邻接表就完成了
*/
static int[] v = new int[N];
static int[] w = new int[N];
static int[][] f = new int[N][N];
private static void add(int a,int b) {//该方法同于向有向图中加入一条边，这条边的起点是a，终点是b，加入的这条边编号为idx
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
private static void dfs(int u) {
for(int i = h[u];i != -1;i = ne[i]) {// 循环物品组，对当前结点的边进行遍历
int son = e[i];//e数组的值是当前边的终点，即儿子结点
dfs(son);
for(int j = m - v[u];j >= 0;j --) {// 循环体积
//遍历背包的容积，因为我们是要遍历其子节点，所以当前节点我们是默认选择的。
//这个时候当前结点我们看成是分组背包中的一个组，子节点的每一种选择我们都看作是组内一种物品，所以是从大到小遍历。
//我们每一次都默认选择当前结点，因为到最后根节点是必选的。
for(int k = 0;k <= j;k ++) {// 循环决策
f[u][j] = Math.max(f[u][j], f[u][j - k] + f[son][k]);
}
}
}
//加上刚刚默认选择的父节点价值
for(int i = m;i >= v[u];i --) f[u][i] = f[u][i - v[u]] + w[u];
//因为我们是从叶子结点开始往上做，所以如果背包容积不如当前物品的体积大，那就不能选择当前结点及其子节点，因此赋值为零
for(int i = 0;i < v[u];i ++) f[u][i] = 0;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int root = 0;
Arrays.fill(h, -1);
for(int i = 1;i <= n;i ++) {
v[i] = sc.nextInt();
w[i] = sc.nextInt();
int p = sc.nextInt();
if(p == -1) {
root = i;
}else {
add(p,i);//如果不是根节点就加入邻接表,其中p是该节点的父节点，i是当前是第几个节点
}
}
sc.close();
dfs(root);
System.out.println(f[root][m]);
}
}
例题：11. 背包问题求方案数
import java.util.Scanner;
public class Main {
static int N = 1010;
static int mod = 1000000007;
static int[] f = new int[N];
static int[] g = new int[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
f[0] = 0;
g[0] = 1;
for(int i = 1;i <= n;i++) {
int v = sc.nextInt();
int w = sc.nextInt();
for(int j = m;j >= v;j --) {
int maxv = Math.max(f[j], f[j - v] + w);
int cnt = 0;
if(maxv == f[j]) cnt = (cnt + g[j]) % mod ;
if(maxv == f[j - v] + w) cnt = (cnt + g[j - v]) % mod;
g[j] = cnt;
f[j] = maxv;
}
}
sc.close();
//f[m]是最大值
int cnt = 0;
for(int i = 0;i <= m;i++)
if(f[i] == f[m])
cnt = (cnt + g[i]) % mod;
System.out.println(cnt);
}
}
例题：734. 能量石
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
static int INF = Integer.MAX_VALUE >> 1;
static int N = 10010;
static int n;
static int[] f = new int[N];
static Stone[] stones = new Stone[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int C = 1;C <= T;C++) {
int m = 0;//总共的时间
n = sc.nextInt();
for(int i = 0;i < n;i++) {
int s = sc.nextInt();
int e = sc.nextInt();
int l = sc.nextInt();
stones[i] = new Stone(s, e, l);
m += s;
}
Arrays.sort(stones, 0, n, new Comparator<Stone>() {
@Override
public int compare(Stone o1, Stone o2) {
return o1.s * o2.l - o2.s * o1.l;
}
});
Arrays.fill(f, -INF);//恰好是j的初始方式
f[0] = 0;
for(int i = 0;i < n;i++) {
int s = stones[i].s;
int e = stones[i].e;
int l = stones[i].l;
for(int j = m;j >= s;j--) {
f[j] = Math.max(f[j], f[j - s] + e - (j - s) * l);
}
}
int res = 0;
for(int i = 0;i <= m;i++) res = Math.max(res, f[i]);
System.out.printf("Case #%d: %d\n", C, res);
}
sc.close();
}
}
class Stone{
int s;
int e;
int l;
public Stone(int s, int e, int l) {
this.s = s;
this.e = e;
this.l = l;
}
}
上一篇： 第一章动态规划（九）
下一篇： 洛谷P1003 铺地毯