次のデータセットの使用の制約

Question

を与えR内の変数の合計を最適化：

ID=c(1:24) 
COST=c(85,109,90,104,107,87,99,95,82,112,105,89,101,93,111,83,113,81,97,97,91,103,86,108) 
POINTS=c(113,96,111,85,94,105,105,95,107,88,113,100,96,89,89,93,100,92,109,90,101,114,112,109) 
mydata=data.frame(ID,COST,POINTS) 

を私は「COST」の合計が固定未満である行のすべての組み合わせを検討するR関数を必要とします値 - この場合は$ 500 - を合計し、合計した 'POINTS'に基づいて最適な選択を行います。

あなたのお手伝いがありがとうございます。

Answer 1

この投稿はまだ開いているので、私は私の解決策を与えるだろうと思った。この種の問題は常に楽しいです。だから、可能なすべての組み合わせ（約2^24、または1600万以上）を順番にチェックすることで、解決策を強制的に試すことができます。これは、各組み合わせについて、その値がその中にあるかどうかを考慮することによって行うことができる。私はこれを実行するために多くの時間がかかるだろう推定

#DO NOT RUN THIS CODE 
for(i in 1:2^24) 
    sum_points[i]<-ifelse(sum(as.numeric((intToBits(i)))[1:24] * mydata$COST) < 500, 
         sum(as.numeric((intToBits(i)))[1:24] * mydata$POINTS), 
         0) 

：あなたはthisポストに触発されたフォロー機能コードを使用することができバイナリで考えます。並列化などで改善できるかもしれませんが、やはりこれはかなり強力な計算です。このメソッドは、1（25個の異なるIDへの増加）が計算時間を2倍にするので、あまりうまく拡張できません。もう一つの選択肢は、少しチートすることです。たとえば、私たちは$ 500以下で滞在しなければならないことを知っています。私たちが最も安価なアイテムを追加した場合、私は間違いなく500ドル以上になるでしょうか？

which(cumsum(sort(mydata$COST))>500) 
[1] 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 

5つ以上のIDが選択されており、間違いなく500ドルを超えています。ほかに何か。

ちょっとしたコードを実行して、その部分の最大値を取って、それが私たちに伝えるものを見ることができます。

sum_points<-1:10000 

for(i in 1:10000) 
    sum_points[i]<-ifelse(sum(as.numeric((intToBits(i)))[1:24]) <6, 
          ifelse(sum(as.numeric((intToBits(i)))[1:24] * mydata$COST) < 500, 
            sum(as.numeric((intToBits(i)))[1:24] * mydata$POINTS), 
            0), 
           0) 
sum_points[which.max(sum_points)] 
[1] 549 

したがって、残りの2^24 - 10000個の選択肢で549ポイント以上を取得しなければなりません。しかし：我々は4つの最高点の値を合計

which(cumsum(rev(sort(mydata$POINTS)))<549) 
[1] 1 2 3 4 

場合でも、我々はまだ549を打ついけない、そうであっても、それらを検索する理由はありません。さらに、考慮する選択肢の数は4より大きくなければならないが、6未満でなければならない。私の腸の感覚は、私が試してみると良い数であると私に伝えている。代わりに、すべての16百万の選択肢を見て、私たちはちょうど24であることを起こるおり、24のうち5を作る方法のすべてを見ることができます5を選択します。

num<-1:choose(24,5) 
combs<-combn(24,5) 

sum_points<-1:length(num) 

    for(i in num) 
    sum_points[i]<-ifelse(sum(mydata[combs[,i],]$COST) < 500, 
         sum(mydata[combs[,i],]$POINTS), 
           0) 
which.max(sum_points) 
[1] 2582 

sum_points[2582] 
[1] 563 

我々は第二千五百八十二反復で新しい最大を持っています。

mydata[combs[,2582],]$ID 
[1] 1 3 11 22 23 

を、何が悪かったのないことを確認するために：：IDを取得するには

sum(mydata[combs[,2582],]$COST) 
[1] 469 #less than 500 

sum(mydata[combs[,2582],]$POINTS) 
[1] 563 #what we expected.