[TIOJ] 1883. pD. 最終幻想

題目連結:http://tioj.infor.org/problems/1883

---

本題看起來很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;
}