题目描述
blablabla
JAVA代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
/**
* 1.为什么不能用完全背包问题的思路去解决
* 因为完全背包没有物品个数限制,所以只要体积够用就可以一直选,没有最后一项。
* 完全背包最后那一项体积是刚好用完了的,而多重背包最后那一项之后还有体积没用完,所以多重背包的式子后面还可以多减一项,而完全背包就不行了。
* 2.优化方法及代码
*
*
* 3.01背包问题的优化写法
* https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.html#%E4%B8%80%E7%BB%B4dp%E6%95%B0%E7%BB%84-%E6%BB%9A%E5%8A%A8%E6%95%B0%E7%BB%84
* @param args
*/
static int N = 12010;
static int M = 2010;
static int v[] = new int[N];
static int w[] = new int[N];//
static int f[] = new int[M];//体积小于M
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s1[] = br.readLine().split(" ");
int n = Integer.parseInt(s1[0]);//物品种数
int m = Integer.parseInt(s1[1]);//背包容积。
int cnt = 0;//分组的组别
for (int i = 1; i <= n; i++) {
String ss[] = br.readLine().split(" ");
int a = Integer.parseInt(ss[0]);
int b = Integer.parseInt(ss[1]);
int s = Integer.parseInt(ss[2]);
int k = 1;//组别里面的个数
/**
* 第一个组1
* 第二个组2
* 第三个组4
* 第四个组8
* ...
*/
while (k <= s){
cnt++;//组别数先增加
v[cnt] = a*k;//这个组的整体体积
w[cnt] = b*k;//这个组的整体价值
s -= k;//s减小
k *= 2;//组别数成倍增加
}
//剩余的最后一组
if(s>0){
cnt++;
v[cnt] = a*s;
w[cnt] = b*s;
}
}
n = cnt;//我们每次要枚举的是组数
//优化后的01背包
for (int i = 1; i <= n; i++) {
for (int j = m; j >= v[i]; j--) {
f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
}
}
System.out.println(f[m]);
}
}