2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1 #include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6  int val[6]= {50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15  {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69 }
2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1#include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6int val[6]={50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69}
2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1#include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6int val[6]={50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69}
2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1#include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6int val[6]={50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69}
2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1#include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6int val[6]={50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69}
2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1#include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6int val[6]={50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69}
2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1#include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6int val[6]={50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69}
2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1#include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6int val[6]={50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69}
2010年8月10日
题意： 输入的第一行为一个正整数N（1<=N<=40)。下面有N行输入数据，每一行第一个数t为找零的总数，后面6个数字m1，m2, m3, m4, m5, m6分别为现有面值为50,20,10,5,2,1纸币的张数。 如果能够找出总数为t的零钱，那么输出最少的张数的方案。如 s1 s2 s3 s4 s5.分别表示为找零面值为50 20 10 5 2 1的张数。si si+1之间用空格 隔开s5后面没有空格。否则输出Refuse。每个输出占一行。 分析：显然背包的容量为 T ，即选择满足容量的最小解。首先对于设 F[i] 表示在背包容量为 i 的情况下的最优解是 cnt[i][0--5]。则F[i]=max(F[i],F[i-w[j]]+w[j]); 如果 F[i]不变，则跟新cnt[i][0--5];
1#include<iostream>
2using namespace std;
3const int maxn=100000;
4
5int s[6];
6int val[6]={50,20,10,5,2,1};
7int v,cnt[maxn][6];
8int f[maxn];
9
10int main()
11{
12 int i,j,k,t,t1,t2;
13 scanf("%d",&t);
14 while(t--)
15 {
16 scanf("%d",&v);
17 for(i=0;i<6;i++)
18 scanf("%d",&s[i]);
19
20 memset(f,0,sizeof(f));
21 memset(cnt,0,sizeof(cnt));
22
23 for(i=0;i<=v;i++)
24 {
25 for(j=0;j<6;j++)
26 {
27 if(i<val[j])continue;
28
29 if(cnt[i-val[j]][j]+1<=s[j])
30 {
31 if(f[i]<f[i-val[j]]+val[j])
32 {
33 f[i]=f[i-val[j]]+val[j];
34
35 for(k=0;k<6;k++)
36 cnt[i][k]=cnt[i-val[j]][k];
37 cnt[i][j]++;
38 }
39 else if(f[i]==f[i-val[j]]+val[j])
40 {
41 t1=0;t2=1;
42 for(k=0;k<6;k++)
43 {
44 t1+=cnt[i][k];
45 t2+=cnt[i-val[j]][k];
46 }
47 if(t2<t1)
48 {
49 for(k=0;k<6;k++)
50 cnt[i][k]=cnt[i-val[j]][k];
51 cnt[i][j]++;
52 }
53 }
54 }
55 }
56 }
57 if(f[v]!=v)
58 {
59 printf("Refuse\n");
60 }
61 else
62 {
63 for(i=0;i<5;i++)
64 printf("%d ",cnt[v][i]);
65 printf("%d\n",cnt[v][5]);
66 }
67 }
68 return 0;
69}
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|