P1314 01背包问题II

Question

问题遇到的现象和发生背景

问题相关代码，请勿粘贴截图

#include<bits/stdc++.h>
using namespace std;
int w[100001],v[100001],dp[100001];
int main()
{
    int t,n,m;
    cin>>t;
    while(t--)
    {
        memset(dp,0,sizeof(dp));
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            cin>>w[i]>>v[i];
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=m;j>=w[i];j--)
            {
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        cout<<dp[m]<<endl;
    }
}

运行结果及报错内容

我的解答思路和尝试过的方法

动态规划

我想要达到的结果

Answer 1

你的代码有2个问题：

1. 数组没必要开那么大，用vector存储即可。
2. 存储状态的数组定义，以及状态转移方程是错的。

按你的思路改写的

int main(int argc, char *argv[])
{
    int t, n, W;
    cin >> t; // 输入测试用例数
    while (t-- > 0)
    {
        cin >> n >> W; // 输入物品数量n、背包（剩余）重量W
        assert(n > 0);
        assert(W > 0);
        
        // 输入n个物品重量、价值
        vector<int> v(n), w(n);
        for (int i = 0; i < n; ++i)
        {
            cin >> w[i] >> v[i];
        }

        vector<vector<int> > c(n + 1, vector<int>(W + 1, 0)); // 全部初始化为0
        // c[i][j] 表示将前i个物品，放入背包剩余重量为j，取得的最大价值

        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= W; ++j)
            {
                int idx = i - 1;
                if (j < w[idx]) // 背包剩余容量不足以放入第i个物品，只有一种选择，价值不变
                {
                    c[i][j] = c[i - 1][j];
                }
                else
                {
                    // 剩余重量足够时，有两种选择，选价值高者
                    c[i][j] = max(c[i - 1][j], c[i - 1][j - w[idx]] + v[idx]);
                }
            }
        }
        cout << c[n][W] << endl;
    }
    return 0;    
}