首页 > 代码库 > POJ 3260 多重背包+完全背包

POJ 3260 多重背包+完全背包

2024-09-18 02:39:55   220人阅读

链接：

http://poj.org/problem?id=3260

题意：

你去买总价为t的东西，每种硬币你有k枚，老板有无数枚，求硬币交换数目最少的数目

题解：

你是多重背包，老板是完全背包，先预处理一下，然后计算取总和最小的就行了

代码：

31 int v[MAXN], c[MAXN];32 int dp1[MAXN], dp2[MAXN];33 int sum[MAXN];34 35 int main() {36     int n, t;37     cin >> n >> t;38     rep(i, 1, n + 1) cin >> v[i];39     rep(i, 1, n + 1) cin >> c[i];40     memset(dp1, 0x3f, sizeof(dp1));41     dp1[0] = 0;42     rep(i, 1, n + 1) {43         memset(sum, 0, sizeof(sum));44         rep(j, v[i], MAXN) if (dp1[j - v[i]] != INF && sum[j - v[i]] < c[i] && dp1[j] > dp1[j - v[i]] + 1)45             dp1[j] = dp1[j - v[i]] + 1, sum[j] = sum[j - v[i]] + 1;46     }47 48     memset(dp2, 0x3f, sizeof(dp2));49     dp2[0] = 0;50     rep(i, 1, n + 1) rep(j, v[i], MAXN) dp2[j] = min(dp2[j], dp2[j - v[i]] + 1);51     int ans = INF;52     rep(i, t, MAXN) ans = min(ans, dp1[i] + dp2[i - t]);53     if (ans == INF) ans = -1;54     cout << ans << endl;55     return 0;56 }

 

POJ 3260 多重背包+完全背包


联系
我们