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

一个案例都过不了

#include <bits/stdc++.h>

using namespace std;

const int N = 102;
const int M = 20010;

int n, m;
int f[M], w[N], v[N];

int main()
{
    cin >> m;
    string s; getline(cin, s);
    getline(cin, s);
    stringstream ssin(s);
    while(ssin >> v[n + 1]) n++;
    for(int i=1; i<=n; i++) cin >> w[i];

    for(int i=1; i<=n; i++)
        for(int j=v[i]; j<=m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[m] << endl;

    return 0;
}
1

我问了一下技术支持,N 最大可以到 910,所以您把 const int N = 102; 改成 const int N = 1000; 就可以通过了,感谢您的反馈,我们修改一下题面。

1

由于「力扣」上没有「完全背包」问题的标准问题,我们自建了这道问题,采用了 ACM 的答题方式,需要大家自行编写输入、输出的逻辑。以下是参考代码:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int W = Integer.parseInt(bufferedReader.readLine());
    
        String line1 = bufferedReader.readLine();
        String line2 = bufferedReader.readLine();
        String[] line1Array = line1.split(" ");
        String[] line2Array = line2.split(" ");
    
        int N = line1Array.length;
        int[] weights = new int[N];
        int[] values = new int[N];
        for (int i = 0; i < N; i++) {
            weights[i] = Integer.parseInt(line1Array[i]);
            values[i] = Integer.parseInt(line2Array[i]);
        }
    
        int[] dp = new int[W + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = weights[i - 1]; j <= W; j++) {
                dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
            }
        }
        System.out.println(dp[W]);
    }
}