2つの拘束を持つナップザック

Question

与えられた問題：

0/1-ナップサックの問題で、n個のアイテムのそれぞれが重みw_iと値v_iを持ちます。重みW.

の重み付けにまとめるアイテムの最大合計値を探す。しかし2 constraitsあります

1. はナップザックのすべての項目の総重量は正確に W する必要があります。
2. の合計額はであり、でもでなければなりません。

両方の制約に注意を払うアルゴリズムを見つけたいと思います。私はすでに一度にどのように私がそれらの1つに注意を払うことができるかを知った。ここで

は1（正確な重量W）をconstraitに注意を払っている私の実装です：

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 

：

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 

そして、ここでは、（アイテムの量さえも）口座に2をconstraitのテイク私の実装です

私は2つの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だけです。

これを単に負の数（整数の最大負の値）に増やすと、現在のアルゴリズムが機能するはずです。