首页 > 代码库 > POJ 3624 Charm Bracelet

POJ 3624 Charm Bracelet

2024-07-11 04:02:52   218人阅读

DP 一直是心中痛，不多说了，这个暑假就坑在这上了。


这暑假第一道DP题，01背包问题。

题意是说物品有 重量和价值 ，但你能承受的重量有限，问你能带的最大价值。


这题数组开大点，虽然不知道有啥坑点，但是我数组开得大，直接1A了。


想想自己DP都是大问题，还要给学弟讲（tiao）题（jiao），真是忧伤。


只能这几天通宵点出 DP 天赋。顺便贴上自己的理解，反正我也准备这样给学弟讲，如果有误，请路过大神指正。



论01背包的自我修养：


        N个物品，M容量的包，最大价值为W。
        
        第 i 件物品分别有 Vi 的重量和 Ci 的价值。
        

            N = 4 ，M= 6 。


            V        C
            
        1：    1        4
        2：    2        6
        3：    3        12
        4：    2        7
        
        int dp[10001],c[10001],v[10001];
        
        //分别为背包的价值，物品的价值，物品重量。
        
        memset(dp,0,sizeof(dp));
        
        //初始化背包    毕竟没放东西的时候是没有价值的
        
        for(int i=0 ; i<n ; i++)
        {
            //从第一件物品开始放
            
            for(int j=m ; j-v[i] >= 0 ; j--)    // j - v[i] >=0防止数组越界，毕竟背包容量不能为负
            {
                //背包每次减去1，看能不能放进去这件物品
                
                //printf("%d:max(%d,%d) ",j,dp[j],dp[j-c[i]]+v[i]);
                
                dp[j] = max ( dp[j] , dp[ j-v[i] ] + c[i] );
            
                //当背包容量为j的时候，能放进去增加价值，就放进去
                
                //dp[j] 容量为j的时候的价值
                
                //dp[ j-c[i] ] + c [i]  （容量j减去当前物品的重量=剩余容量） 的价值 + 当前物品的价值
                
                //价值当然越大越好 取max
                
                //当 j - v[i] < 0表明背包已经不能放了。
            }
            
        }
        
        容量：max（前一个价值，放入当前物品后的价值）
        
        6 :max(0,4)         5 :max(0,4)         4 :max(0,4)         3 :max(0,4)         2 :max(0,4)         1 :max(0,4)
        6 :max(4,10)       5 :max(4,10)       4 :max(4,10)       3 :max(4,10)       2 :max(4,6)
        6 :max(10,22)     5 :max(10,18)     4 :max(10,16)     3 :max(10,12)
        6 :max(22,23)     5 :max(18,19)     4 :max(16,13)     3 :max(12,11)     2 :max(6,7)
        
        
        最后背包 从容量 0 ~ 6 所能有的价值，取其最大值。
        

        M：W      0        1        2        3          4         5          6


                         0:0     1:4     2:7     3:12     4:16     5:19     6:23
                
        
        这时候背包装满的情况 价值W最大，为23。
        






#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
using namespace std;
int dp[1000001];
int c[100001],v[100001];
int n,m;

int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
            scanf("%d%d",&c[i],&v[i]);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            for(int j=m;j-c[i]>=0;j--)
            {
                dp[j]=max(dp[j],dp[j-c[i]]+v[i]);
            }
        }
        int ans=0;
        for(int i=0;i<=m;i++)
            ans=max(ans,dp[i]);
            printf("%d\n",ans);
    }
}



联系
我们