Product Development
Product Development
题目大意
一个项目需要k个物品都至少到达p个数量; 现在有n个套餐, 每个套餐都可以给这k个物品加若干个数量, 每个套餐都要各自的价格; 请问在满足项目要求的情况下需要的最小花费是多少;
题解思路
在一定限制内，求其成本最小化，与01背包中，在一定范围内，价值最大化，有异曲同工之处，所以这里使用01背包的思想，需要注意的是，这里说的是至少参数为k，所以可以大于等于k，那么在取其值的时候，如果当前的最小取值不再是该计划的参数增加值，而是0，这样的话，当最终为k的时候，其真实情况中，该物品的参数可以是大于等于k的
1 #include <iostream>
2 #include<math.h>
3 #include<string.h>
4 #define int long long
5 using namespace std;
6 const int N = 109;
7 int n, m, k;
8 int c[N], s[N][N];
9 int dp[9][9][9][9][9];
10 void solve() {
11 cin >> n >> m >> k;
12 for (int i = 1; i <= n; i++) {
13 cin >> c[i];
14 for (int j = 0; j < m; j++) {
15 cin >> s[i][j];
16 }
17 }
18
19 //初始化，初始化的值一定要大
20 for (int h1 = 0; h1 <= k; h1++) {
21 for (int h2 = 0; h2 <= k; h2++) {
22 for (int h3 = 0; h3 <= k; h3++) {
23 for (int h4 = 0; h4 <= k; h4++) {
24 for (int h5 = 0; h5 <= k; h5++) {
25 dp[h1][h2][h3][h4][h5] = 1e12 + 10;
26 }
27 }
28 }
29 }
30 }
31
32
33 //01背包思想
34 dp[0][0][0][0][0]=0;
35 for (int i = 1; i <= n; i++) {
36 for (int h1 = k; h1 >= 0; h1--) {
37 for (int h2 = k; h2 >= 0; h2--) {
38 for (int h3 = k; h3 >= 0; h3--) {
39 for (int h4 = k; h4 >= 0; h4--) {
40 for (int h5 = k; h5 >= 0; h5--) {
41 int s1=max(h1-s[i][0],0ll);
42 int s2=max(h2-s[i][1],0ll);
43 int s3=max(h3-s[i][2],0ll);
44 int s4=max(h4-s[i][3],0ll);
45 int s5=max(h5-s[i][4],0ll);
46 int &t=dp[s1][s2][s3][s4][s5];
47 int &tt=dp[h1][h2][h3][h4][h5];
48 tt=min(tt,t+c[i]);
49 }
50 }
51 }
52 }
53 }
54 }
55
56 //如果小于m表示当前样例中没有该物品
57 int d[6];
58 for(int i=0;i<5;i++)
59 {
60 if(i<m) d[i]=k;
61 else d[i]=0;
62 }
63
64 //可能会出现所有计划都不能使每个物品都为k的情况
65 int dd=dp[d[0]][d[1]][d[2]][d[3]][d[4]];
66 if(dd>=1e12) cout<<"-1\n";
67 else cout<<dd<<"\n";
68 }
69 signed main() {
70 ios::sync_with_stdio(0);
71 cin.tie(0);
72 cout.tie(0);
73 solve();
74 return 0;
75 }