背包九讲总结
n件物品，背包容量为m。 物品体积为v，价值为w。
01背包模板
for(int i
= 0; i
< n
; i
++) {
for(int j
= m
; j
>= v
[i
]; j
--) {
dp
[j
] = Math
.max(dp
[j
], dp
[j
- v
[i
]] + w
[i
]);
}
}
System
.out
.println(dp
[m
]);
完全背包模板
for(int i
= 0; i
< n
; i
++) {
for(int j
= v
[i
]; j
<= m
; j
++) {
dp
[j
] = Math
.max(dp
[j
], dp
[j
- v
[i
]] + w
[i
]);
}
}
System
.out
.println(dp
[m
]);
多重背包问题
每件物品最多有s件。
for(int i
= 0; i
< n
; i
++) {
for(int j
= m
; j
>= v
[i
]; j
--) {
for(int k
= 1; k
* v
[i
] <= j
&& k
<= s
[i
]; k
++) {
dp
[j
] = Math
.max(dp
[j
], dp
[j
- k
* v
[i
]] + k
* w
[i
]);
}
}
}
System
.out
.println(dp
[m
]);
多重背包的二进制优化
import java
.util
.Scanner
;
import java
.util
.ArrayList
;
public class Main {
public static void main(String
[] args
) {
Scanner in
= new Scanner(System
.in
);
int n
= in
.nextInt();
int m
= in
.nextInt();
int[] v
= new int[n
];
int[] w
= new int[n
];
int[] s
= new int[n
];
int[] dp
= new int[m
+ 5];
for(int i
= 0; i
< n
; i
++) {
v
[i
] = in
.nextInt();
w
[i
] = in
.nextInt();
s
[i
] = in
.nextInt();
}
ArrayList
<Good> ls
= new ArrayList<Good>();
for(int i
= 0; i
< n
; i
++) {
for(int k
= 1; k
<= s
[i
]; k
*= 2) {
s
[i
] -= k
;
ls
.add(new Good(v
[i
] * k
, w
[i
] * k
));
}
if(s
[i
] > 0) ls
.add(new Good(v
[i
] * s
[i
], w
[i
] * s
[i
]));
}
for(int i
= 0; i
< ls
.size(); i
++) {
for(int j
= m
; j
>= ls
.get(i
).v
; j
--) {
dp
[j
] = Math
.max(dp
[j
], dp
[j
- ls
.get(i
).v
] + ls
.get(i
).w
);
}
}
System
.out
.println(dp
[m
]);
}
static class Good {
int v
, w
;
public Good(int v
, int w
) {
this.v
= v
;
this.w
= w
;
}
}
}
import java
.util
.Scanner
;
public class Main {
public static void main(String
[] args
) {
Scanner in
= new Scanner(System
.in
);
int n
= in
.nextInt();
int m
= in
.nextInt();
int[] v
= new int[n
];
int[] w
= new int[n
];
int[] s
= new int[n
];
int[] dp
= new int[m
+ 5];
for(int i
= 0; i
< n
; i
++) {
v
[i
] = in
.nextInt();
w
[i
] = in
.nextInt();
s
[i
] = in
.nextInt();
}
int[] tv
= new int[n
* 10];
int[] tw
= new int[n
* 10];
int tot
= 0;
for(int i
= 0; i
< n
; i
++) {
for(int k
= 1; k
<= s
[i
]; k
<<= 1) {
s
[i
] -= k
;
tv
[tot
] = v
[i
] * k
;
tw
[tot
++] = w
[i
] * k
;
}
if(s
[i
] > 0) {
tv
[tot
] = v
[i
] * s
[i
];
tw
[tot
++] = w
[i
] * s
[i
];
}
}
for(int i
= 0; i
< tot
; i
++) {
for(int j
= m
; j
>= tv
[i
]; j
--) {
dp
[j
] = Math
.max(dp
[j
], dp
[j
- tv
[i
]] + tw
[i
]);
}
}
System
.out
.println(dp
[m
]);
}
}
混合背包问题
s等于-1表示物品只能用1次， 0表示能用无限次， 大于零表示能用s次。
import java
.util
.Scanner
;
import java
.util
.ArrayList
;
public class Main {
public static void main(String
[] args
) {
Scanner in
= new Scanner(System
.in
);
int n
= in
.nextInt();
int m
= in
.nextInt();
int v
, w
, s
;
int[] dp
= new int[m
+ 10];
ArrayList
<Node> ls
= new ArrayList<Node>();
for(int i
= 0; i
< n
; i
++) {
v
= in
.nextInt();
w
= in
.nextInt();
s
= in
.nextInt();
if(s
< 0) ls
.add(new Node(-1, v
, w
));
else if(s
== 0) ls
.add(new Node(0, v
, w
));
else {
for(int k
= 1; k
<= s
; k
<<= 1) {
s
-= k
;
ls
.add(new Node(-1, v
* k
, w
* k
));
}
if(s
> 0) ls
.add(new Node(-1, v
* s
, w
* s
));
}
}
Node now
;
for(int i
= 0; i
< ls
.size(); i
++) {
now
= ls
.get(i
);
if(now
.kind
< 0) {
for(int j
= m
; j
>= now
.v
; j
--) {
dp
[j
] = Math
.max(dp
[j
], dp
[j
- now
.v
] + now
.w
);
}
} else {
for(int j
= now
.v
; j
<= m
; j
++) {
dp
[j
] = Math
.max(dp
[j
], dp
[j
- now
.v
] + now
.w
);
}
}
}
System
.out
.println(dp
[m
]);
}
static class Node {
int kind
, v
, w
;
public Node(int kind
, int v
, int w
) {
this.kind
= kind
;
this.v
= v
;
this.w
= w
;
}
}
}
