[Offer刈り取り]プログラミング練習試合11テーマ2:アイテム価値

時間制限:10000 ms
単点時間:1000 ms
メモリ制限:256 MB
説明
Hiさんは今n個の品物を持っていて、すべての品物に価値があります.そして、このn個の物品には全部でm個の異なる属性があり、各物品にはいくつかの属性がある.
Hoちゃんはその中からいくつかのアイテムを選び、属性ごとにちょうど奇数のアイテムが所有していることを満たし、選ばれたアイテムの価値の総和が最も大きい.Hoさんの任務を完成させるのを手伝ってもらえますか.
入力
1行目の数T(<=10)は、データ群数を表す.各グループのデータについて:
1行目の2つの数n,m(1<=n<=1000,m<=10)
次に2行ごとに1つの品物を説明します.各アイテムについて:
最初の行の2つの数vとsは、その価値と属性の数(v<=100000,s<=m)を表します.
2行目のs個の数は、その物品が持つ属性番号(1<=番号<=m)を示す
しゅつりょく
物品価値合計の最大値.
サンプル入力

1
3 2
2 1
1
2 1
2
5 2
1 2

サンプル出力

5

構想
状態圧縮DP.
ステータス定義:
dp[i][j]は、オプションが[0,i]の場合、各属性パリティ状態がjの最大価値を表す.
状態遷移:
i番目のアイテムを選択しない場合、dp[i][j]=max(dp[i][j],dp[i-1][j]);
i番目のアイテムを選択すると、dp[i][s 1]=max(dp[i][s 1],dp[i-1][j]+v[i])となり、そのうちs 1 = j^p[i]は、物品iの添加後に発生した状態遷移に対応する.
コード#コード#

 1 import java.util.Arrays;
 2 import java.util.Scanner;
 3 
 4 public class Main {
 5 
 6     public static int resolve(int[] v, int[] p, int n, int m) {
 7         final int STATES = 1 << m;
 8         int[][] dp = new int[n + 1][STATES];
 9         for (int i = 0; i <= n; i++) {
10             Arrays.fill(dp[i], -1);
11         }
12 
13         dp[0][0] = 0;
14         for (int i = 1; i <= n; i++) {
15             for (int j = 0; j < STATES; j++) {
16                 if (dp[i - 1][j] < 0)
17                     continue;
18                 dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
19                 int s1 = j ^ p[i - 1];
20                 dp[i][s1] = Math.max(dp[i][s1], dp[i - 1][j] + v[i - 1]);
21             }
22         }
23 
24         return dp[n][STATES - 1];
25     }
26 
27     public static void main(String[] args) {
28         Scanner sc = new Scanner(System.in);
29         int t = sc.nextInt();
30         while (t-- > 0) {
31             int n = sc.nextInt();
32             int[] v = new int[n];
33             int[] p = new int[n];
34             int m = sc.nextInt();
35             for (int i = 0; i < n; i++) {
36                 v[i] = sc.nextInt();
37                 int pcnt = sc.nextInt();
38                 for (int j = 0; j < pcnt; j++) {
39                     p[i] |= (1 << (sc.nextInt() - 1));
40                 }
41             }
42 
43             System.out.println(resolve(v, p, n, m));
44         }
45     }
46 }

 
転載先:https://www.cnblogs.com/deadend/p/6665626.html