1924: 01背包-C++

解题思路:

注意事项:

参考代码:

#include<iostream>
using namespace std;
int N;//物品个数
int C;//背包容量
int v[1000],w[10000];//物品价值、重量
int dp[1000][10000];
void traceback();
int main()
{
    cin>>N>>C;
    for(int i=1;i<=N;i++)   cin>>w[i]>>v[i];

    for(int i=1;i<=N;i++)           //从一号物品进行遍历
        for(int j=0;j<=C;j++)       //j表示背包可用空间
        {
            if(j<w[i])              //如果容量不够，自动继承装入上一个物品时的价值
                dp[i][j]=dp[i-1][j];
            else                    //容量够，比较装入和不装入的价值，选择较大的
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
    cout<<dp[N][C];
    //cout<<endl;
    //traceback();
}
//查看装入物品的编号，本题用不到，忽略！
void traceback()
{
    int temp=C;
    int x[N+1];
    for(int i=N;i>=1;i--)
        if(dp[i][temp]==dp[i-1][temp])
            x[i]=0;
        else
        {
            temp-=w[i];
            x[i]=1;
        }
    for(int i=1;i<=N;i++)
        if(x[i]==1)
        cout<<i<<" ";
    cout<<endl;
    return;
}