1 solutions

  • 0
    @ 2022-8-28 19:03:16

    01+贪心,具体看代码

    #include<iostream>
    using namespace std;
    int volume[1010],value[1010];//定义储存物品体积和价值的数组 
    int ans[1010][1010];//定义储存答案的数组 
    int t,N,V;
    int main()
    {
    	cin>>V>>N;  //输入物品数和背包体积 
    	for(int i=1;i<=N;i++)//输入各个物品的属性 
    		cin>>value[i]>>volume[i];
    	for(int i=N;i>=1;i--) //从后往前遍历物品求后几个物品的最优解 
    	{
    		for(int j=0;j<=V;j++)//因为数组是二维的所以体积怎样遍历都可以 
    		{
    		    ans[i][j]=ans[i+1][j];
    		    if(j>=volume[i])
    			    ans[i][j]=max(ans[i][j],ans[i+1][j-volume[i]]+value[i]);//状态转移方程 
    		}
    	}
    	int nowvolume=V;//记录当前体积 
    	for(int i=1;i<=N;i++)//从第一个物品开始遍历 
    	{
    		if( volume[i]<=nowvolume && ans[i][nowvolume]==ans[i+1][nowvolume-volume[i]]+value[i] )
    		{//判段这个物品是否可选能选就选尽量选小同时要确保当前背包体积能装下此物品 
    			cout<<i<<" ";//输出物品编号 
    			nowvolume-=volume[i];//选择一个物品当前体积要相应减少 
    		}
    	}
    	return 0;
    }
    
    • 1

    Information

    ID
    6532
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    7
    Tags
    # Submissions
    42
    Accepted
    15
    Uploaded By