有2個約束的揹包

Question

給定問題：

0/1-揹包問題，每個項目有n個權重w_i和值v_i。查找其權重之和高達體重W.

但有兩個constraits的最大總價值：

1. 總重量所有項目在揹包的需要是準確W¯¯。
2. 總計數量項目必須是甚至。

我想找到一個關注兩個約束的算法。我已經發現我一次可以關注其中的一個。

這是我實現它注重constrait 1（準確重量W）：

public class KnapSackExactWeight { 
    public static void main(String[] args) { 
     int[] w = new int[] {4, 1, 5, 8, 3, 9, 2}; //weights 
     int[] v = new int[] {2, 12, 8, 9, 3, 4, 3}; //values 

     int n = w.length; 
     int W = 10; // W (max weight) 

     int[][] DP = new int[n+1][W+1]; 

     for(int i = 1; i < n+1; i++) { 
      for(int j = 0; j < W+1; j++) { 
       if(i == 0 || j == 0) { 
        DP[i][j] = 0; 
       } else if (j - w[i-1] >= 0) { 
        DP[i][j] = Math.max(DP[i-1][j], DP[i-1][j - w[i-1]] + v[i-1]); 
       } else { 
        DP[i][j] = -Integer.MAX_VALUE; 
       } 
      } 
     } 
     System.out.println("Result: " + DP[n][W]); 
    } 
} 

Result: 22 

這裏是我實現這需要constrait 2考慮（甚至量的項目）：

public class KnapSackEvenAmount { 
    public static void main(String[] args) { 
     int[] weights = new int[] {4, 1, 5, 8, 3, 9, 2}; //weights 
     int[] values = new int[] {2, 12, 8, 9, 3, 4, 3}; //values 

     int n = weights.length; 
     int W = 10; 

     int[][] DP_odd = new int[n+1][W+1]; 
     int[][] DP_even = new int[n+1][W+1]; 

     for(int i = 0; i < n+1; i++) { 
      for(int j = 0; j < W+1; j++) { 
       DP_even[i][j] = -1; 
       DP_odd[i][j] = -1; 
       if(i == 0 || j == 0) { 
        DP_odd[i][j] = -1; 
        DP_even[i][j] = 0; 
       } else if(j - weights[i-1] >= 0) { 
        if(DP_odd[i-1][j - weights[i-1]] >= 0) { 
         DP_even[i][j] = Math.max(DP_even[i-1][j], DP_odd[i-1][j - weights[i-1]] + values[i-1]); 
        } 
        if(DP_even[i-1][j - weights[i-1]] >= 0) { 
         DP_odd[i][j] = Math.max(DP_odd[i-1][j], DP_even[i-1][j - weights[i-1]] + values[i-1]); 
        } 
       } 
       if(i > 0) { 
        DP_odd[i][j] = Math.max(DP_odd[i][j], DP_odd[i-1][j]); 
        DP_even[i][j] = Math.max(DP_even[i][j], DP_even[i-1][j]); 
       } 
      } 
     } 
     System.out.println("Result: " + DP_even[n][W]); 
    } 
} 

Result: 21 

這樣做的想法是：我使用兩個DP表格（DP_even和DP_odd），併爲DP_odd中的奇數項目和DP_even中的項目均勻的項目保存最佳解決方案。

現在我的問題是如何實現這兩個約束一起工作。有沒有辦法解決這個問題？

（如果有什麼是我的問題不清楚，只問！）

Answer 1

不知道，如果是做這個問題，但我在這裏要做的是首先減少的問題，以適應約束的最佳途徑。首先找到可能的偶數重者等於揹包重量的物品，然後找到最高值

import java.util.Scanner; 
import static java.lang.Math.pow; 

public class subSet{ 

void subset(int num,int n, int x[]) 
{ 
    int i; 
    for(i=1;i<=n;i++) 
     x[i]=0; 
    for(i=n;num!=0;i--) 
    { 
     x[i]=num%2; 
     num=num/2; 
    } 
} 
public static void main(String[] args) { 
    int n,d,sum,present=0; 
    int j; 
    System.out.println("enter the number of items"); 
    Scanner sc=new Scanner(System.in); 
    n=sc.nextInt(); 
    int a[]=new int[n+1]; 
    int x[]=new int[n+1]; 
    System.out.println("enter the weights of items"); 
    for(int i=1;i<=n;i++) 
     a[i]=sc.nextInt(); 
    System.out.println("enter the values of items"); 
    int v[]=new int[n+1]; 
    for(int i=1;i<=n;i++) 
     v[i]=sc.nextInt(); 
    System.out.println("enter the max weight"); 
    d=sc.nextInt(); 

    int sol=0;int max=0; 
    if(d>0) 
    { 
     for(int i=1;i<=Math.pow(2,n)-1;i++) 
     { 
      subSet s=new subSet(); 
      s.subset(i,n,x); 
      sum=0;int count=0; 
      for(j=1;j<=n;j++) 
       if(x[j]==1) 
       { 
        sum=sum+a[j]; 
        count++; 
       } 
      sol=0; 
      if(d==sum && count%2==0) 
      { 
       present=1; 
       for(j=1;j<=n;j++) 
       { 
        if(x[j]==1) 
         sol=v[j]+sol; 
        if(sol>max) 
         max=sol; 
       } 
      } 

     } 

    } 
    if(present==0) 
     System.out.println("Solution does not exists"); 
    else 
     System.out.print("solution = "+max); 

} 
} 

Answer 2

我想問題可能是這一行的組合：

DP_odd[i][j] = -1; 

你給一個點球只有1次使用了奇數次。

如果你只是把這個增加到一個更大的負數（例如整數的最大負值），我認爲你當前的算法應該工作。