來源
以下是自己寫的
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]);
}
}
多重背包
題目：輸入數(shù)據(jù)首先包含一個正整數(shù)C，表示有C組測試用例，每組測試用例的第一行是兩個整數(shù)n和m(1<=n<=100, 1<=m<=100),分別表示經(jīng)費的金額和大米的種類，然后是m行數(shù)據(jù)，每行包含3個數(shù)p，h和c(1<=p<=20,1<=h<=200,1<=c<=20)，分別表示每袋的價格、每袋的重量以及對應(yīng)種類大米的袋數(shù)。對于每組測試數(shù)據(jù)，請輸出能夠購買大米的最多重量，你可以假設(shè)經(jīng)費買不光所有的大米，并且經(jīng)費你可以不用完。每個實例的輸出占一行。
定理：一個正整數(shù)n可以被分解成1,2,4,…,2(k-1),n-2k+1（k是滿足n-2k+1>0的最大整數(shù)）的形式，且1～n之內(nèi)的所有整數(shù)均可以唯一表示成1,2,4,…,2(k-1),n-2^k+1中某幾個數(shù)的和的形式.
證明如下：
（1） 數(shù)列1,2,4,…,2(k-1),n-2k+1中所有元素的和為n，所以若干元素的和的范圍為：[1, n]；
（2）如果正整數(shù)t<= 2^k – 1,則t一定能用1,2,4,…,2(k-1)中某幾個數(shù)的和表示，這個很容易證明：我們把t的二進(jìn)制表示寫出來，很明顯，t可以表示成n=a0*20+a12^1+…+ak2^（k-1），其中ak=0或者1，表示t的第ak位二進(jìn)制數(shù)為0或者1.
（3）如果t>=2k,設(shè)s=n-2k+1，則t-s<=2k-1，因而t-s可以表示成1,2,4,…,2(k-1)中某幾個數(shù)的和的形式，進(jìn)而t可以表示成1,2,4,…,2^(k-1)，s中某幾個數(shù)的和（加數(shù)中一定含有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];
//關(guān)鍵
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];
}
}
