讨论/《零起步学算法》 - 练习:01 背包问题/
《零起步学算法》 - 练习:01 背包问题
共 26 个回复

看着纯黑的代码框,一瞬间有些恍然不知所措……

11

发个Python3的dp

n=int(input())
weights=list(map(int,input().split()))
values=list(map(int,input().split()))
a=len(weights)
dp=[[0 for _ in range(n+1)]for _ in range(a+1)]
for i in range(1,a+1):
    for j in range(1,n+1):
        if j>=weights[i-1]:
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i-1]]+values[i-1])
        else:
            dp[i][j]=dp[i-1][j]
print(dp[a][n])
4

这才是笔试的正确打开方式

2

为什么只能通过4个测试用例,能不能放出所有测试用例?

public class Solution {
    public static void main(String[] args) throws IOException {
        // 初始化输入 参考 weiwei 哥提供的代码
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        // w 背包能承担的最大负担
        int w = Integer.parseInt(bufferedReader.readLine());
        String line1 = bufferedReader.readLine();
        String line2 = bufferedReader.readLine();
        String[] line1Array = line1.split(" ");
        String[] line2Array = line2.split(" ");
        // n 所有物品数量
        int n = line1Array.length;
        // weight 第 i 个物品的重量; value 第 i 个物品的价值
        int[] weight = new int[n];
        int[] value = new int[n];

        for(int i=0; i<n; i++) {
            weight[i] = Integer.parseInt(line1Array[i]);
            value[i] = Integer.parseInt(line2Array[i]);
        }

        // 动态规划设计 dp[i][j] 表示拿到第 i 件物品时,背包空间为 j 可以拿到的最大价值
        // dp[i][j] = dp[i-1][j]                        // 第 i 件物品不拿
        //          = dp[i-1][j-weight[i]] + value[i]  //  第 i 件物品拿,腾出负担值
        int[][] dp = new int[n+1][w+1];
        
        // 状态转移 [TO DO]优化一维空间
        for(int i=1; i<=n; i++){
            for(int j=weight[i-1]; j <=w; j++){
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1]);
            }
        }
        // 返回值
        System.out.println(dp[n][w]);
    }
}
1

C++(头文件有点多😓)

#include <iostream>
#include <algorithm>
#include <tuple>
#include <bitset>
#include <regex>
#include <fstream>
#include <sstream>
#include <random>
#include <iomanip> 
#include <functional>
#include <unordered_map>
#include <stack>
#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <numeric>
using namespace std;

int main() {
	int maxWeight;
	cin >> maxWeight;
	cin.ignore();
	string s;
	getline(cin, s);
	//cout << s << endl;
	istringstream ss(s);
	string weight,value;
	vector<int> weights;
	while (ss >> weight) {
		weights.push_back(stoi(weight));
	}
	getline(cin, s);
	ss.clear();
	ss.str(s);
	vector<int> values;
	while (ss >> value) {
		values.push_back(stoi(value));
	}
	int n = values.size();
	vector<int> dp(maxWeight + 1);
	for (int i = 1; i <=n; i++) {
		for (int j = maxWeight; j>0; j--) {
			if(j-weights[i-1]>=0)
				dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
		}
	}
	cout << dp[maxWeight];
}

1

这是我到今天为止2021力扣提交错误次数最多的题

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

const int N = 2010;
int wei[N], val[N], dp[N][N];
int n, W;

int main(){
    string s;
    int pos = 0;

    cin >> W;
    getchar();
    getline(cin, s);
    while(pos < s.length()){
        int len = 0, tmp = 0;
        while(pos + len < s.length() && s[pos + len] != ' '){
            tmp = tmp * 10 + s[pos + len] - '0';
            ++ len;
        }
        wei[++ n] = tmp;
        pos += len + 1;
    }

    for(int i = 1; i <= n; i ++)
        cin >> val[i];

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= W; j ++){
            dp[i][j] =  max(dp[i - 1][j], dp[i][j - 1]);
            if(j >= wei[i])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - wei[i]] + val[i]);
        }
    }
    cout << dp[n][W] << endl;
    return 0;
}
#include <iostream>
#include <string>
#include <cstring>

using namespace std;

const int N = 2010;
int wei[N], val[N], dp[N];
int n, W;

int main(){
    string s;
    int pos = 0;

    cin >> W;
    getchar();
    getline(cin, s);
    while(pos < s.length()){
        int len = 0, tmp = 0;
        while(pos + len < s.length() && s[pos + len] != ' '){
            tmp = tmp * 10 + s[pos + len] - '0';
            ++ len;
        }
        wei[++ n] = tmp;
        pos += len + 1;
    }

    for(int i = 1; i <= n; i ++)
        cin >> val[i];

    for(int i = 1; i <= n; i ++)
        for(int j = W; j >= wei[i]; j --)
                dp[j] = max(dp[j], dp[j - wei[i]] + val[i]);

    cout << dp[W] << endl;
    return 0;
}
1

压缩空间复杂度到O(n), 这个输入有点憨憨啊= =
另外开101和201居然会炸, 难道输入范围不对么= =

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

int dp[1001];
int weight[2001];
int val[1001];
int main(){
    int n;
    cin>>n;
    int cnt = 0;
    int tmp;
    while(cin>>tmp){
        weight[cnt++] = tmp;
    }
    for(int i=cnt/2; i<cnt;i++){
        val[i - cnt/2] = weight[i];
    }
    for(int i=0;i<cnt / 2;i++){
        for(int j=n; j>=weight[i];j--){
            dp[j] = max(dp[j- weight[i]]  + val[i], dp[j]);
        }
    }
    cout<<dp[n]<<endl;
    return 0;
}
1
#include<bits/stdc++.h>
using namespace std;

int main()
{
    int W, n, maxv = 0;
    vector<int> arr;
    cin >> W;
    while(cin >> n)
        arr.push_back(n);
    n = arr.size()/2;
    vector<int> w(arr.begin(), arr.begin()+n);
    vector<int> v(arr.begin()+n, arr.end());
    vector<int> dp(W+1, -1);
    dp[0] = 0;
    for(int i = 0; i < n; ++i)
    {
        for(int j = W-w[i]; j >= 0; --j)
        {
            if(dp[j] != -1)
            {
                dp[j+w[i]] = max(dp[j+w[i]], dp[j]+v[i]);
                maxv = max(maxv, dp[j+w[i]]);
            }
        }
    }
    cout << maxv << endl;
    return 0;
}

0ms 3.3MB

1

原来是这样,这种写法还真没学过,以为写案例默认这样输入

好久没有自己写输入输出:

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 1000+5;
int dp[maxn];
int main(){
    int W;
    cin >> W;
    vector<int> weights,values;
    int n;
    while(cin >> n){
        weights.push_back(n);
    }
    for(int i = 0;i < weights.size() / 2;i++){
        values.push_back(weights[weights.size() /2 + i]);
    }

    memset(dp,0,sizeof dp);
    int m = weights.size();
    for(int i = 0;i < m / 2;i++){
        for(int j = W; j >= weights[i];j--){
            dp[j] = max(dp[j],dp[j-weights[i]] + values[i]);
        }
    }
    cout << dp[W] << endl;
    return 0;
}