[TIOJ] 1883. pD. 最終幻想
題目連結:http://tioj.infor.org/problems/1883
本題看起來很0/1背包吧,不過它跟普通的0/1背包不同的點在於它的物品是無限個的,因此這類問題又被稱作完全背包問題,那完全背包問題該如何做呢,不難發現原本0/1背包問題在滾動的時候要從後面滾是為了維護它不會重複取,不過我們現在不就是要讓它能重複取嗎?,所以其實就把0/1背包原本從後面倒過來做的,改成從前面做就好了
本題看起來很0/1背包吧,不過它跟普通的0/1背包不同的點在於它的物品是無限個的,因此這類問題又被稱作完全背包問題,那完全背包問題該如何做呢,不難發現原本0/1背包問題在滾動的時候要從後面滾是為了維護它不會重複取,不過我們現在不就是要讓它能重複取嗎?,所以其實就把0/1背包原本從後面倒過來做的,改成從前面做就好了
#include <bits/stdc++.h>
using namespace std;
struct skill{
int cost, damage;
};
skill mySkills[1000 + 5];
int dmg[10000 + 5];
int main(){
int t;
scanf("%d",&t);
while(t--){
int w,b,n,m;
scanf("%d%d%d",&w,&b,&n);
for(int i=0;i<=w;i++){
dmg[i]=0;
}
for(int i=0;i<n;i++){
scanf("%d%d",&mySkills[i].cost,&mySkills[i].damage);
}
scanf("%d",&m);
for(int i=0;i<n;i++){
mySkills[i].cost+=m;
}
for(int i=0;i<n;i++){
for(int j=mySkills[i].cost;j<w;j++){
dmg[j] = max(dmg[j], dmg[j-mySkills[i].cost]+mySkills[i].damage);
}
}
if(dmg[w-1] >= b)
puts("Yes");
else
puts("No");
}
return 0;
}
留言
張貼留言