0-1背包基础（一）

题目

由于每一个物品只有一件，我们很容易想到，先计算它的总体价值，然后根据 t o t a t V a l u e = v a l u e / s p a c e 可以得到一个物品的总体价值。

0 – 1背包问题

具体思路

1. 确定遍历的顺序，因为总共是一个物品，所以我们要确定我们的物品不能重复取到，也就是避免写出完全背包的代码。可以想象为，遇到好的物品，但是我们只能取一次，不能一直取的问题。
2. dp[j - kindsSpace[i]] 的计算一定是不能依靠更新过了的值，本轮循环是确定什么时候能够唯一的取到这个物品。

所以压缩成一维数组的话，一定要改变容量的遍历顺序，否则容易取好几次同一个物品。

具体实现

import java.util.Scanner;

class Main{
    public static void main(String[] s){
        Scanner scan = new Scanner(System.in);
        int kindsNum = 0;
        int space = 0;
        kindsNum = scan.nextInt();
        space = scan.nextInt();
        int[] kindsSpace = new int[kindsNum + 1];
        int[] kindsValues = new int[kindsNum + 1];

        for(int i = 1; i <= kindsNum; i++){
            kindsSpace[i] = scan.nextInt();
        }
        for(int i = 1; i <= kindsNum; i++){
            kindsValues[i] = scan.nextInt();
        }

        int[] dp = new int[space + 1];

        for(int i = 1; i <= kindsNum; i++){
            for(int j = space; j > 0; j--){
                if(j >= kindsSpace[i]){
                    dp[j] = Math.max(dp[j], dp[j - kindsSpace[i]] + kindsValues[i]);    
                }
            }
        }

        System.out.println(dp[space]);
    }
}

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int num = 0;
    int size = 0;
    cin >> num >> size;
    vector<int> weight(num + 1, 0);
    vector<int> value(num + 1, 0);
    for (int i = 1; i <= num; i++)
    {
        cin >> weight[i];
    }
    for (int i = 1; i <= num; i++)
    {
        cin >> value[i];
    }
    // 1.dp数组时指向当前有多少的大小取到的最大容量；
    vector<int> dp(size + 1, 0);
    for (int i = 1; i <= num; i++)
    {
        // 关键点在于从后向前遍历
        // 否则会重复相加，犯了和之前一样的错误，[i-1]而不是[i]
        for (int j = size; j >= 0; j--)
        {
            if (j >= weight[i])
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[size];
    return 0;
}
/**************************************************************
    Problem: 1046
    User: odCYZ6pM-Br5MD5myV8LZ6FO1iWw [kamaCoder22960]
    Language: C++
    Result: 正确
    Time:53 ms
    Memory:2176 kb
****************************************************************/