hdu 01リュックサックまとめ(1171+2546+1864+2955...
7373 ワード
1171
题意は比较的に简単で、この问题の比较的に特别な地方は01リュックサックの中で、すべての物体は1つの価値があって1つの重さがあって、比较的に価値が最大で、重さは制限されて、この问题は価値が制限されている情况の下で最大で、同じく値は01リュックサックの中の重さを価値に変えます.
2546
上と同じように、重さがなく、価値しかありません.
カードに5元未満の場合は、元の値を出力します.5元より大きい場合は、m-5の範囲で最も多くのお金(最も高い料理を残す)を使って、残りのお金で最も高い料理を減らします.
コード#コード#
2602
水問題、書きません.基本01リュックサック.
1864
題意は簡単で、作り方も簡単で、すべて*100が整数になって01リュックサックになります.
一箇所(int)(q*100)うっかり書きました(int)q*100は長い間デバッグしてやっと見つけました、バカ==
この問題も別の方法で作ることができて、枚数でリュックサックになります.
私たちの普段のリュックサックは品質で、データが大きすぎるとき、あるいはこれのように実数で、思考を転換することができて、価値でリュックサックなどになります.
2955
また整数ではない問題で、この問題は前のように簡単にx 100で完成できないことがわかります.精度が足りないからです.
確率をリュックサックにすることができて、この問題はもう1か所異なってプラスするかどうか、確率は乗るのです
题意は比较的に简単で、この问题の比较的に特别な地方は01リュックサックの中で、すべての物体は1つの価値があって1つの重さがあって、比较的に価値が最大で、重さは制限されて、この问题は価値が制限されている情况の下で最大で、同じく値は01リュックサックの中の重さを価値に変えます.
//Problem : 1171 ( Big Event in HDU ) Judge Status : Accepted
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int v[6000], dp[5000 * 50 + 10];
int main() {
//freopen("in.txt", "r", stdin);
int n;
int sum;
while (scanf("%d", &n) != EOF && n >= 0) {
memset(dp, 0, sizeof(dp));
int a, b;
sum = 0;
int idx = 0;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a, &b);
sum += a * b;
for (int j = 0; j < b; j++) {
v[++idx] = a;
}
}
for (int i = 1; i <= idx; i++)
for (int j = sum / 2; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
printf("%d %d
", sum - dp[sum / 2], dp[sum / 2]);
}
return 0;
}
2546
上と同じように、重さがなく、価値しかありません.
カードに5元未満の場合は、元の値を出力します.5元より大きい場合は、m-5の範囲で最も多くのお金(最も高い料理を残す)を使って、残りのお金で最も高い料理を減らします.
コード#コード#
//Problem : 2546 ( ) Judge Status : Accepted
#include <iostream>
#include <algorithm>
using namespace std;
int v[1005];
int dp[1005];
int main()
{
int n, m;
while (cin >> n && n) {
memset(dp, 0, sizeof(dp)); // wa 。。。
for (int i = 1; i <= n; ++i) {
cin >> v[i];
}
cin >> m;
if (m < 5) {
printf("%d
", m);
continue;
}
sort(v + 1, v + n + 1);
for (int i = 1; i < n; ++i) {
for (int j = m - 5; j >= v[i]; j--)
dp[j] = max(dp[j], dp[j - v[i]] + v[i]);
}
printf("%d
", m - dp[m - 5] - v[n]);
}
return 0;
}
2602
水問題、書きません.基本01リュックサック.
1864
題意は簡単で、作り方も簡単で、すべて*100が整数になって01リュックサックになります.
一箇所(int)(q*100)うっかり書きました(int)q*100は長い間デバッグしてやっと見つけました、バカ==
//Problem : 1864 ( ) Judge Status : Accepted
/**< hdu 1864 */
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
double pri[35]; //
int pric[35];
int dp[35 * 1000 * 100];
int main()
{
double q;
int n, m;
double pri_a, pri_b, pri_c;
while (scanf("%lf%d", &q, &n) != EOF && n) {
int idx = 0;
for (int i = 0; i < n; ++i) {
cin >> m;
pri_a = pri_b = pri_c = 0;
char ch;
double price;
int ok = 1;
for (int j = 0; j < m; ++j) {
scanf(" %c:%lf", &ch, &price);
switch(ch) {
case 'A' :
pri_a += price;
break;
case 'B' :
pri_b += price;
break;
case 'C' :
pri_c += price;
break;
default: ok = 0;
}
}
double sum = pri_a + pri_b + pri_c;
//printf("a=%f,b=%f,c=%f,sum=%f
", pri_a, pri_b, pri_c, sum);
if (!(pri_a > 600 || pri_b > 600 || pri_c > 600 || sum > 1000) && ok) pri[++idx] = sum;
} //end for pri[]
for (int i = 1; i <= idx; i++) {
pric[i] = (int)(pri[i] * 100);
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= idx; ++i) {
for (int j = (int)(q * 100); j >= pric[i]; --j) {
dp[j] = max( dp[j], dp[j - pric[i]] + pric[i]);
}
}
printf("%.2f
", dp[(int)(q * 100)] / 100.00);
}
return 0;
}
この問題も別の方法で作ることができて、枚数でリュックサックになります.
私たちの普段のリュックサックは品質で、データが大きすぎるとき、あるいはこれのように実数で、思考を転換することができて、価値でリュックサックなどになります.
//Problem : 1864 ( ) Judge Status : Accepted
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
double pri[35];
double dp[35];
int main()
{
double q;
int n, m;
double pri_a, pri_b, pri_c;
while (scanf("%lf%d", &q, &n) != EOF && n) {
int idx = 0;
for (int i = 0; i < n; ++i) {
cin >> m;
pri_a = pri_b = pri_c = 0;
char ch;
double price;
int ok = 1;
for (int j = 0; j < m; ++j) {
scanf(" %c:%lf", &ch, &price);
switch(ch) {
case 'A' :
pri_a += price;
break;
case 'B' :
pri_b += price;
break;
case 'C' :
pri_c += price;
break;
default: ok = 0;
}
}
double sum = pri_a + pri_b + pri_c;
//printf("a=%f,b=%f,c=%f,sum=%f
", pri_a, pri_b, pri_c, sum);
if (!(pri_a > 600 || pri_b > 600 || pri_c > 600 || sum > 1000) && ok) pri[++idx] = sum;
} //end for pri[]
for (int i = 0; i <= idx; i++) {
dp[i] = 0.0;
}
for (int i = 1; i <= idx; ++i) {
for (int j = idx; j >= 1; --j) {
if (dp[j - 1] + pri[i] <= q)
dp[j] = max(dp[j], dp[j - 1] + pri[i]);
}
}
double ans = 0;
for (int i = 1; i <= idx; ++i)
if (ans < dp[i]) ans = dp[i];
printf("%.2f
", ans);
}
return 0;
}
2955
また整数ではない問題で、この問題は前のように簡単にx 100で完成できないことがわかります.精度が足りないからです.
確率をリュックサックにすることができて、この問題はもう1か所異なってプラスするかどうか、確率は乗るのです
//Problem : 2955 ( Robberies ) Judge Status : Accepted
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
double P[105]; //
int M[105]; // ...
double dp[10005];
int main()
{
int t;
cin >> t;
while (t--) {
int n;
int sum = 0;
double p;
cin >> p >> n;
for (int i = 1; i <= n; ++i) {
cin >> M[i] >> P[i];
P[i] = 1 - P[i];
sum += M[i];
}
memset(dp, 0, sizeof(dp));// wa 。。。
dp[0] = 1; // 1
for (int i = 1; i <= n; ++i) {
for (int j = sum; j >= M[i]; --j) {
dp[j] = max(dp[j], dp[j - M[i]] * P[i]); //
}
}
for (int i = sum; i >= 0; --i)
if (dp[i] > 1 - p) {
printf("%d
", i);
break;
}
}
return 0;
}