首页 > 代码库 > [再做01背包] POJ 3624 Charm Bracelet

[再做01背包] POJ 3624 Charm Bracelet

2024-07-12 17:47:13   219人阅读

接触动态规划的第一题是数塔问题，第二题就是01背包问题了。

当时看的懵懵懂懂，回过头来再看这道题还是非常简单的了。

用 dp[i][j] 表示取前i种物品，使它们总体积不超过j的最优取法取得的价值总和
状态转移方程：dp[i][j] = max(dp[i-1][j],dp[i-1][j-cost[i]]+weight[i])

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 const int maxn = 13000 + 10; 8 int dp[maxn]; 9 int cost[3500], weight[3500];10 11 int main(void)12 {13     #ifdef LOCAL14         freopen("3624in.txt", "r", stdin);15     #endif16 17     int n, v;18     int i;19     scanf("%d%d", &n, &v);20     memset(dp, 0, sizeof(dp));21     for(i = 1; i <= n; ++i)22         scanf("%d%d", &cost[i], &weight[i]);23 24     int j;25     for(i = 1; i <= n; ++i)26         for(j = v; j >= cost[i]; --j)27         {28             dp[j] = max(dp[j], dp[j-cost[i]] + weight[i]);29         }30 31     printf("%d\n", dp[v]);32     return 0;33 }
代码君


联系
我们