image.png
image.png
来源
以下是自己写的
import java.util.Scanner;
public class test{
public static void main(String[] args){
int totalPersons = 10;
int[] value = {500, 200, 300, 350, 400};
int[] persons = {5, 3, 4, 3, 5};
//这里储存整个maxMatri，实际上只用到了前一行，所以和上面的代码相比浪费空间了。
int[][] maxMatri = new int[value.length][totalPersons + 1];
for(int i = persons[0]; i < totalPersons + 1; ++i){
maxMatri[0][i] = value[0];
}
for(int i = 1; i < value.length; ++i){
for( int j = 1; j < totalPersons + 1; ++j){
maxMatri[i][j] =j - persons[i] >= 0 ? Math.max(maxMatri[i - 1][j], maxMatri[i - 1][j - persons[i]] + value[i]) : maxMatri[i -1][j];
}
}
System.out.println(maxMatri[maxMatri.length - 1][maxMatri[0].length - 1]);
}
}
import java.util.Scanner;
public class test{
/**
* more concise
*/
public static void main(String[] args){
int totalPersons = 10;
int[] value = {500, 200, 300, 350, 400};
int[] persons = {5, 3, 4, 3, 5};
int[] maxProfit = new int[totalPersons + 1];
for(int i = 0; i < value.length; ++i){
for( int j = totalPersons; j >= persons[i]; --j){
if( i == 0){
maxProfit[j] = value[i];
continue;
}
maxProfit[j] = Math.max(maxProfit[j], maxProfit[j - persons[i]] + value[i]);
if( i == value.length -1 && j == totalPersons)
break;
}
}
System.out.println(maxProfit[totalPersons]);
}
}
01背包
也可以这么解
import java.util.Scanner;
public class test{
public static void main(String[] args){
//weight
int [] w = {2,2,6,5,4};
//value
int [] v = {6,3,5,4,6};
System.out.println(package01(w, v, 10));
}
private static int package01(int w[], int v[], int totalW){
/**
* This method wastes memory
*/
// int[] preF = new int[totalW + 1];
// int[] f = new int[totalW + 1];
// for(int i = 0; i < w.length; ++i){
// for(int j = 0; j < totalW + 1; ++j){
// if(j == 0){
// preF[j] = w[0];
// continue;
// }
// f[j] = j - w[i] > 0? Math.max(preF[j], preF[j - w[i]] + v[i]) : preF[j];
// }
// for(int j = 1; j < totalW + 1; ++j){
// preF[j] = f[j];
// }
// }
int [] maxp = new int [totalW + 1];
for(int i = 0; i < w.length; ++i){
for(int j = totalW; j >= w[i]; --j){
maxp[j] = Math.max(maxp[j], maxp[j - w[i]] + v[i]);
}
}
return maxp[totalW];
}
}
完全背包
只需修改为
for(int i = 0; i < w.length; ++i){
for(int j = w[i]; j < totalW+1; ++j){
maxp[j] = Math.max(maxp[j], maxp[j - w[i]] + v[i]);
}
}
多重背包
题目：输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分别表示每袋的价格、每袋的重量以及对应种类大米的袋数。对于每组测试数据，请输出能够购买大米的最多重量，你可以假设经费买不光所有的大米，并且经费你可以不用完。每个实例的输出占一行。
定理：一个正整数n可以被分解成1,2,4,…,2(k-1),n-2k+1（k是满足n-2k+1>0的最大整数）的形式，且1～n之内的所有整数均可以唯一表示成1,2,4,…,2(k-1),n-2^k+1中某几个数的和的形式.
证明如下：
（1） 数列1,2,4,…,2(k-1),n-2k+1中所有元素的和为n，所以若干元素的和的范围为：[1, n]；
（2）如果正整数t<= 2^k – 1,则t一定能用1,2,4,…,2(k-1)中某几个数的和表示，这个很容易证明：我们把t的二进制表示写出来，很明显，t可以表示成n=a0*20+a12^1+…+ak2^（k-1），其中ak=0或者1，表示t的第ak位二进制数为0或者1.
（3）如果t>=2k,设s=n-2k+1，则t-s<=2k-1，因而t-s可以表示成1,2,4,…,2(k-1)中某几个数的和的形式，进而t可以表示成1,2,4,…,2^(k-1)，s中某几个数的和（加数中一定含有s）的形式。
（证毕！）
import java.util.ArrayList;
import java.util.Scanner;
public class test{
/**
* more concise
*/
public static void main(String[] args){
int money = 8;
int[] value = {2,4};
int[] weight = {100, 100};
int[] amount = {4, 2};
System.out.println(multiplePackage(money, value, weight, amount));
}
private static int multiplePackage(int money, int[] value, int[] weight, int[] amount){
int[] dp = new int[money + 1];
//关键
ArrayList<Integer> valueList = new ArrayList<>();
ArrayList<Integer> weightList = new ArrayList<>();
for(int i = 0; i < value.length; ++i){
for(int j = 1; j < amount[i]; j <<= 1){
valueList.add(value[i] * j);
weightList.add(weight[i] * j);
amount[i] -= j;
}
if(amount[i] > 0){
valueList.add(amount[i] * value[i]);
weightList.add(amount[i] * weight[i]);
}
}
//还是01背包的解法
for(int i = 0; i < valueList.size(); ++i){
for(int j = money; j >= valueList.get(i); --j){
if( dp[j] < dp[j - valueList.get(i)] + weightList.get(i)){
dp[j] = dp[j - valueList.get(i)] + weightList.get(i);
}
}
}
return dp[money];
}
}
网友评论