01背包

问题

有N个物品要装到一个只能承重W的背包里，每个物品重量为w[i]（weight），价值为v[i]（value），问背包能装的最大价值

前提

每类物品只能装一个（此谓01）。

二维解法

/*01背包二维数组解决*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N,W; //物品种类数,背包总能承受重量
    cin >> N >> W;
    int w[N+1]; //每个物品的重量,从1开始
    int v[N+1]; //每个物品的价值,从1开始
    int dp[N+1][W+1]; //dp[i][j]表示考虑第i个物品,总重量为j时,能达到的最大价值
    for(int i=1;i<=N;i++) cin >> w[i] >> v[i]; //重量 价值
    for(int i=0;i<=N;i++) for(int j=0;j<=W;j++) dp[i][j]=0;
    for(int i=1;i<=N;i++) for(int j=W;j>=w[i];j--) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); //(不用第i个物品,用第i个物品)
    cout << dp[N][W];
    return 0;    
}

一维解法

int main()
{
    int N,W; //物品种类数,背包总能承受重量
    cin >> N >> W;
    int w[N+1]; //每个物品的重量,从1开始
    int v[N+1]; //每个物品的价值,从1开始
    int dp[W+1]; //dp[i][j]表示考虑第i个物品,总重量为j时,能达到的最大价值
    for(int i=1;i<=N;i++) cin >> w[i] >> v[i]; //重量 价值
    for(int i=0;i<=W;i++) dp[i]=0;
    for(int i=1;i<=N;i++) for(int j=W;j>=w[i];j--) dp[j] = max(dp[j],dp[j-w[i]]+v[i]); //(不用第i个物品,用第i个物品)
    cout << dp[W];
    return 0;    
}

示例

输入

10 15
2 3
3 4
4 8
5 8
9 10
3 5
4 6
2 4
6 7
7 9

输出

26

完全背包

关于我

关于我