POJ charm bracelet 背包问题
本题的POJ测试网址:http://bailian.openjudge.cn/practice/4131/
以下是我的代码,其实是看了别人的分析写的。我感觉这样写思路应该是没问题的,但是一直没在POJ上通过,结果一直是Wrong Answer,苦恼
#include
using namespace std;
#include
#define Max_N 3402
#define Max_M 12880
int N, M;
int w[Max_N], value[Max_N],sumfee[Max_M];
int main()
{
cin >> N >> M;
for (int i = 1; i <= N; i++)
cin >> w[i] >> value[i];
for (int i = 0; i <= M; i++)
sumfee[i] = 0;
for (int i = 1; i <= N; i++)
{
for (int v = M; v >=w[i]; v--)
{
sumfee[v] = max(sumfee[v], sumfee[v - w[i]] + value[i]);//滚动数组
}
}
cout << sumfee[M] << endl;
return 0;
}
怎么是英文??
// dtgh.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n=4,w=6;
vector<vector<int>> dp(n+1,vector<int>(w+1));
vector<vector<int>> nums{ {1, 4},{2,6},{3,12},{2, 7} };
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if(nums[i-1][0]>j){
dp[i][j]=dp[i-1][j];
}
else {
dp[i][j]=max((dp[i-1][j-nums[i-1][0]]+nums[i-1][1]),dp[i-1][j]);
}
}
}
cout<<dp[n][w];
}