1 条题解

  • 0
    @ 2023-8-7 11:20:10
    依赖背包
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <map>
    #include <cstring>
    #include <iomanip>
    const int N = 32000 + 10;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    
    struct node{
    	int w , v , w1 ,v1 , w2 , v2;
    }a[70];
    
    int m , n , dp[N] ,x , y , z;
    
    int main()
    {
    	cin >> m >> n;
    	for(int i = 1 ; i <= n; i++)
    	{
    		cin >> x >> y >> z;//x是价格  y重要度  z主件
    		if( !z )//主件 
    		{
    			a[i].w = x;
    			a[i].v = x * y; 
    		} 
    		else//附件 
    		{
    			if(a[z].v1)
    			{
    				a[z].w2 = x;
    				a[z].v2 = x * y;
    			}
    			else
    			{
    				a[z].w1 = x;
    				a[z].v1 = x * y;
    			}
    		}
    	}
    
    	for(int i = 1 ; i <= n; i++)
    	{
    		if(!a[i].v)	continue;
    		for(int j = m; j >= a[i].w; j--)
    		{
    			//考虑  不买 ,买主件 
    			dp[j] = max(dp[j] , dp[j - a[i].w] + a[i].v);
    			if(j >= a[i].w + a[i].w1)//买主 + 附1 
    				dp[j] = max(dp[j] , dp[j - a[i].w - a[i].w1] + a[i].v + a[i].v1); 
    			if(j >= a[i].w + a[i].w2)//买主 + 附2 
    				dp[j] = max(dp[j] , dp[j - a[i].w - a[i].w2] + a[i].v + a[i].v2);
    				
    			if(j >= a[i].w + a[i].w1 + a[i].w2)//买主 + 附1  + 附2 
    				dp[j] = max(dp[j] , dp[j - a[i].w - a[i].w1 - a[i].w2] + a[i].v + a[i].v1 + a[i].v2);
    		 }
    	}
    	cout << dp[m];
    	return 0;
    }
    

    借鉴了张老师的代码

    • 1

    信息

    ID
    688
    时间
    1000ms
    内存
    128MiB
    难度
    5
    标签
    递交数
    100
    已通过
    39
    上传者