perogram

【C++】next_permutation, inner_productの練習

想定

  • 7つお菓子がある
  • 3つ買っていいよと言われた場合
  • どんな買い方と合計金額になるかを列挙

コード

#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

template < typename T >
void vprint(T &V){
    for(auto v : V){
        cout << v << " ";
    }
    cout << endl;
}

const ll mod = 1e9 + 7;
const ll inf = 1e18;
int main() {
    vector<int> A = {150, 300, 350, 400, 450, 600, 650};
    vector<int> F = {1, 1, 1, 0, 0, 0, 0};
    sort(ALL(F));
    
    do {
        vprint(F);

        // 内積
        ll price = inner_product(ALL(A), F.begin(), 0);
        pn(price);
        cout << endl;
    } while (next_permutation(ALL(F)));


}

コンパイル

g++ -std=c++11 experiment.cpp && ./a.out

出力

0 0 0 0 1 1 1
price 1700

0 0 0 1 0 1 1
price 1650

0 0 0 1 1 0 1
price 1500

0 0 0 1 1 1 0
price 1450

0 0 1 0 0 1 1
price 1600

0 0 1 0 1 0 1
price 1450

0 0 1 0 1 1 0
price 1400

0 0 1 1 0 0 1
price 1400

0 0 1 1 0 1 0
price 1350

0 0 1 1 1 0 0
price 1200

0 1 0 0 0 1 1
price 1550

0 1 0 0 1 0 1
price 1400

0 1 0 0 1 1 0
price 1350

0 1 0 1 0 0 1
price 1350

0 1 0 1 0 1 0
price 1300

0 1 0 1 1 0 0
price 1150

0 1 1 0 0 0 1
price 1300

0 1 1 0 0 1 0
price 1250

0 1 1 0 1 0 0
price 1100

0 1 1 1 0 0 0
price 1050

1 0 0 0 0 1 1
price 1400

1 0 0 0 1 0 1
price 1250

1 0 0 0 1 1 0
price 1200

1 0 0 1 0 0 1
price 1200

1 0 0 1 0 1 0
price 1150

1 0 0 1 1 0 0
price 1000

1 0 1 0 0 0 1
price 1150

1 0 1 0 0 1 0
price 1100

1 0 1 0 1 0 0
price 950

1 0 1 1 0 0 0
price 900

1 1 0 0 0 0 1
price 1100

1 1 0 0 0 1 0
price 1050

1 1 0 0 1 0 0
price 900

1 1 0 1 0 0 0
price 850

1 1 1 0 0 0 0
price 800

ちょうどいい問題があった

https://atcoder.jp/contests/abc028/submissions/4011628

注意点

  • next_permutatoinを使うときはその配列を事前ソートしておくこと