救命，零一背包WA70

常规
1

#include<bits/stdc++.h>
using namespace std;
int n,W,sum,dp[10010];
int w[110],v[110];
int main()
{
scanf(“%d%d”,&n,&W);
for(int i=1;i<=n;i++)
{
scanf(“%d%d”,&w[i],&v[i]);
sum+=v[i];
}
memset(dp,sizeof dp,0x3f);
dp[0]=0;
for(int i=1;i<=n;i++)
{
for(int j=v[i];j<=sum;j++)
{
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
}
}
for(int i=sum;i>=1;i–)
{
//cout<<i<<" “<<dp[i]<<endl;
if(dp[i]<=W)
{
printf(”%d\n",i);
return 0;
}
}
return 0;
}

7 个赞
2 
#include<bits/stdc++.h>
using namespace std;
int n,W,sum,dp[10010];
int w[110],v[110];
int main()
{
    scanf("%d%d",&n,&W); 
    for(int i=1;i<=n;i++)
    {
    	scanf("%d%d",&w[i],&v[i]);
    	sum+=v[i]; 
	}
	memset(dp,sizeof dp,0x3f);
	dp[0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=v[i];j<=sum;j++)
		{
			dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
		}
	}
	for(int i=sum;i>=1;i--)
	{
		//cout<<i<<" "<<dp[i]<<endl;
		if(dp[i]<=W)
		{
			printf("%d\n",i);
			return 0;
		}
	}
    return 0;
}
6 个赞
3

@李杜
参考一下标准的01背包（不是你那题，仅供参考。）

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1010];
int w[21], c[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    int flag = 1;
    for (int i = 1; i <= N; i++) {
        for(int j = V; j >= c[i]; j--) {
            dp[j] = max(dp[j], dp[j - c[i]] + w[i]);
        }        
    }
    cout << dp[V] << endl;
    return 0;
}
6 个赞
4

看下你的memset是不是有问题

看下你这里的循环顺序，我们是求01背包，一维的时候是不是应该倒序。

下次提问类别还是选竞赛段吧

8 个赞