有2个约束的背包

Z时代
2024-01-10
分类：问答

给定问题：有2个约束的背包

0/1-背包问题，每个项目有n个权重w_i和值v_i。查找其权重之和高达体重W.

但有两个constraits的最大总价值：

总重量所有项目在背包的需要是准确W¯¯。

总计数量项目必须是甚至。

我想找到一个关注两个约束的算法。我已经发现我一次可以关注其中的一个。

这是我实现它注重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中的项目均匀的项目保存最佳解决方案。

现在我的问题是如何实现这两个约束一起工作。有没有办法解决这个问题？

（如果有什么是我的问题不清楚，只问！）

回答：

不知道，如果是做这个问题，但我在这里要做的是首先减少的问题，以适应约束的最佳途径。首先找到可能的偶数重者等于背包重量的物品，然后找到最高值

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); 
} 
}