Acwing_12. 背包问题求具体方案_dp

Acwing_12. 背包问题求具体方案_dp

//
#include<bits/stdc++.h>
using namespace std;

const int N=1111;
int x[N],y[N],dp[N][N],ans[N];
int n,v,pos;

void f( int id,int v )
{
    if( id==n+1 ) return ;              // 判越界

        // 判越界
    if( v>=x[id] && dp[id][v]==dp[id+1][v-x[id]]+y[id] ) 
    {
        ans[++pos]=id; v-=x[id];        // 可存 也可输出
    }
    f( id+1,v );
}

int main()
{
    int i,j;

    while( cin>>n>>v )
    {
        for( i=1;i<=n;i++ ) cin>>x[i]>>y[i];

        memset( dp,0,sizeof( dp ) );
        for( i=n;i;i-- )                    
            for( j=0;j<=v;j++ )                                     // +
                dp[i][j]=( j>=x[i] )?( max( dp[i+1][j],dp[i+1][j-x[i]]+y[i] ) ):( dp[i+1][j] );
            // {
            //     dp[i][j]=dp[i+1][j];
            //     if( j>=x[i] )
            //         dp[i][j]=max( dp[i][j],dp[i+1][j-x[i]]+y[i] );
            // }
            // cout<<dp[1][v]<<endl;
        pos=0;
        f( 1,v );
		
        for( i=1;i<=pos;i++ )
        {
            if( i!=1 ) cout<<" ";
            cout<<ans[i];
        }
        cout<<endl;
    }
    return 0;
}
// 题目要求输出字典序最小的解，
// 假设存在一个包含第1个物品的最优解，
// 为了确保字典序最小那么我们必然要选第一个。
// 那么问题就转化成从2-N这些物品中找到最优解。

// 之前的 dp[i][j] 记录的都是前i个物品总容量为j的最优解，
// 那么我们现在将 dp[i][j] 定义为从第i个元素到最后一个元素总容量为j的最优解

// dp[i][j]=max( dp[i+1][j],dp[i+1][j-x[i]]+y[i] )
// 两种情况
//     01 不选第i个物品，那么最优解等于 从第i+1个物品到最后一个元素 总容量为j的最优解
//     02 选了第i个物品，那么最优解等于 当前物品的价值y[i] 加上从第i+1个物品到最后一个元素 总容量为j-x[i]的最优解

// 计算完状态表示后 考虑如何的到最小字典序的解
// 首先 dp[1][v] 肯定是最大价值 那么我们便开始考虑能否选取第1个物品呢

// 01 如果 dp[1][v] == dp[2][v-x[1]]+y[1]  说明选取了第1个物品可以得到最优解
// 02 如果 dp[1][v] == dp[2][v]            说明不选取第一个物品才能得到最优解
// 03 如果 dp[1][v] == dp[2][v] == dp[2][v-x[1]]+y[1]
//         说明选不选都可以得到最优解，但是为了考虑字典序最小，我们也需要选取该物品