teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

1

加筆修正

2019/07/06 22:54

投稿

majiponi
majiponi

スコア1722

answer CHANGED
@@ -4,4 +4,64 @@
4
4
 
5
5
  後はループを回すだけです。
6
6
 
7
- キーワードは、ビット操作、インクリメントです。
7
+ ググるためのキーワードは、ビット操作、インクリメントです。
8
+
9
+
10
+ 追記:具体化するとどうなる? とご指摘を頂いたので、あまり本人のためにならないかもですが、コードを書きます。
11
+ ```C
12
+ #include <stdlib.h>
13
+
14
+ int main(void)
15
+ {
16
+ int n;// up to 32
17
+ int maxweight;
18
+ int weight[32];
19
+ int value[32];
20
+ int maxvalue = 0;
21
+ int i, e, j, w, v;
22
+
23
+ printf("品物の数");
24
+ scanf("%d", &n);
25
+ if(n < 1 || 32 < n){
26
+ printf("ERROR!\n");
27
+ exit(0);
28
+ }
29
+ printf("重さと価値\n");
30
+ for(i = 0; i < n; i++){
31
+ scanf("%d , %d", &weight[i], &value[i]);
32
+ if( weight[i] < 1 || 100 < weight[i] || value[i] < 1 || 100 < value[i]){
33
+ printf("ERROR!\n");
34
+ exit(0);
35
+ }
36
+ }
37
+ printf("求める総和");
38
+ scanf("%d", &maxweight);
39
+ if(maxweight < 1 || 10000 < maxweight){
40
+ printf("ERROR!\n");
41
+ exit(0);
42
+ }
43
+
44
+ e = 1 << n;
45
+ for(i = 1; i != e;){
46
+ w = 0;
47
+ v = 0;
48
+ for(j = 0; j < n; j++){
49
+ if(i & (1 << (n - 1 - j))){
50
+ w += weight[j];
51
+ v += value[j];
52
+ }
53
+ }
54
+ if(w > maxweight){
55
+ i += (i & -i);
56
+ }
57
+ else{
58
+ if(v > maxvalue){
59
+ maxvalue = v;
60
+ }
61
+ i++;
62
+ }
63
+ }
64
+
65
+ return 0;
66
+ }
67
+ ```