大礼包
题目
思路
有人用状压做的，不太喜欢，所以我用的dfs，写起来要清晰许多。
代码
class Solution {
public:
int shoppingOffers(vector
<int>& price
, vector
<vector
<int>>& special
, vector
<int>& needs
) {
int sum
=0;
for(int i
=0;i
<price
.size();i
++)
sum
+=price
[i
]*needs
[i
];
for(int i
=0;i
<special
.size();i
++)
{
bool f
=1;
int j
;
for(j
=0;j
<price
.size();j
++)
{
if(needs
[j
]<special
[i
][j
]) f
=0;
needs
[j
]-=special
[i
][j
];
}
if(f
) sum
=min(sum
,shoppingOffers(price
,special
,needs
)+special
[i
][j
]);
for(int j
=0;j
<price
.size();j
++)
needs
[j
]+=special
[i
][j
];
}
return sum
;
}
};
